[Algorithm] 백준 4963 섬의 개수

[ 문제 ]

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

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

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

[ 입력 ]

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다.
• w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

 

[ 출력 ]

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

 

[ 입력 예제 ]

1 1

0

2 2

0 1

1 0

3 2

1 1 1

1 1 1

5 4

1 0 1 0 0

1 0 0 0 0

1 0 1 0 1

1 0 0 1 0

5 4

1 1 1 0 1

1 0 1 0 1

1 0 1 0 1

1 0 1 1 1

5 5

1 0 1 0 1

0 0 0 0 0

1 0 1 0 1

0 0 0 0 0

1 0 1 0 1

0 0

 

[ 출력 예제 ]

0

1

1

3

1

9

 

---

import java.util.*;
import java.io.*;

public class Main {
	
	static int w, h;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
	
	static class Node {
		int x, y;
		Node(int x, int y){
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	public static void bfs(int y, int x) {
		Queue<Node> queue = new LinkedList<>();
		Node current = new Node(x, y);
		queue.offer(current);
		visited[y][x] = true;
		
		while (!queue.isEmpty()) {
			current = queue.poll();
			
			for (int d = 0; d < 8; d++) {
				if (current.x + dx[d] >= 0 && current.x + dx[d] < w && current.y + dy[d] >= 0 && current.y + dy[d] < h
						&& !visited[current.y+dy[d]][current.x+dx[d]] && map[current.y+dy[d]][current.x+dx[d]] == 1) {
					visited[current.y+dy[d]][current.x+dx[d]] = true;
					queue.offer(new Node(current.x+dx[d], current.y+dy[d]));
				}
			}
		}
	}
	

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));;
		StringTokenizer st;
		
		while (true) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken()); // 지도의 너비
			h = Integer.parseInt(st.nextToken()); // 지도의 높이
			
			if (w == 0 && h == 0) break;
			
			map = new int[h][w];
			
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++)
					map[i][j] = Integer.parseInt(st.nextToken()); // 1:땅, 0:바다
			}
			
			visited = new boolean[h][w];
			
			int cnt = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (!visited[i][j] && map[i][j] == 1) { // 방문하지 않았고, 땅인 경우
						cnt++;
						bfs(i, j);
					}
				}
			}
			
			System.out.println(cnt);
		}		
	}
}