[백준 알고리즘]백준 4963번 자바 BFS(너비 우선 탐색)

조건

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

풀이

1. 입력받은 w와 h의 값으로 map[h][w]  지도를 나타내는 2단 배열을 만들어준다.

2. w와 h를 활용하여 2단 반복문을 만들어 모든 가로줄과 세로줄을 다 반복할 수 있도록 한다.

3. 반복중에 섬의 위치를 나타내는 노드의 x,y 값이 나오고 방문했던 노드가 아니면 bfs를 실행한다.

4. 큐에 x, y값을 저장하고 poll 반환 이후 xy와 상하좌우대각 총 8부분중 x y 위치에 있는 섬과 연결된 섬을 큐에 추가해준다. 이때 x y가 0또는 w-1, h-1 위치라면 맨 끝이므로 예외 가정문을 하나 만들어준다.

5. 이 과정을 반복한다(BFS)

6. BFS과정을 몇번 반복했는지를 카운트 해주고 출력해준다.

7. 1~6과정을 while으로 반복해주고 w h 가 0이나오면 반복문 탈출하게 해준다.

 

과정을 보여주자면 이렇다

 

예제 입력 예시

5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1

node[0,0] = 1이기때문에 큐를 생성하여 너비우선 탐색을 해준다

node[0,0]을 poll(반환) 해주고 node[0, 0] 에서 이동가능한 (1,0) 과 (0,1)을 큐에 넣어준다

위에 활동을 반복하면 결과는 이렇다

위의 예시는 그림처럼 한번의 너비우선탐색으로 끝나기때문에 1이 출력된다

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int[][] visited;//방문한 섬, 방문하면 1로 변경
	static int map[][];//지도
	static int queue_x[] = {-1, -1, -1, 0 , 1, 1,  1,  0};
	static int queue_y[] = {-1,  0,  1, 1,  1, 0, -1, -1};
	static StringBuilder sb = new StringBuilder();
	static class Node
	{
		int x, y;
		public Node(int x, int y)
		{
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
		int w = 1;
		int h = 1;
		
		while(true)
		{	
			String line = br.readLine();
			StringTokenizer st = new StringTokenizer(line);
			w = Integer.parseInt(st.nextToken()); //가로
			h = Integer.parseInt(st.nextToken()); //세로
			if(w == 0 && h == 0)
			{
				break;
			}
			map = new int[h][w];
			visited = new int[h][w];		
			for(int  i = 0; i<h; i++)
			{
				String line2 = br.readLine();
				StringTokenizer st2 = new StringTokenizer(line2);
				for(int j = 0; j<w; j++)
				{
					map[i][j] = Integer.parseInt(st2.nextToken());
					visited[i][j] = 0;
				}
			}
			
			bfs(w, h);
		}
		System.out.println(sb);
	}
	
	static void bfs(int w, int h) {
		int count = 0;
		for(int i = 0; i<h; i++)
		{
			for(int j = 0; j<w; j++)
			{
			
				if(map[i][j] == 1 && visited[i][j] == 0)
				{
					  // BFS 구현을 위한 큐(Queue) 생성
				    Queue<Node> queue = new LinkedList<>();
				    // 현재 노드를 방문한 것으로 표시하고 큐에 삽입(enqueue)
					visited[i][j] = 1;
					Node node1 = new Node(i,j);
					queue.add(node1);
					count++;
					// 큐(Queue)가 빌 때까지 반복
					while (!queue.isEmpty()) {
						// 방문한 노드를 큐에서 추출(dequeue)하고 x,y를 저장한 노드 생성
						Node front_Node = queue.poll();
						for(int t = 0; t<8; t++)
						{
							int x = front_Node.x + queue_x[t];
							int y = front_Node.y + queue_y[t];
							if(x >=0 && y>=0 && x<h&&y<w)
							{
								if(map[x][y] == 1 && visited[x][y] == 0)
								{
									Node node2 = new Node(x,y);
									visited[x][y] = 1;
									queue.add(node2);
								}
							}
						}
					}
				}
			}
			
		}
		sb.append(count+"\n");
	}
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/4963