[BOJ 4963] 섬의 개수

문제

• BOJ 4963번
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

for문으로 map배열을 돌면서 집을 발견하고 아직 방문하지 않은 경우 큐에 좌표값을 넣어준다. 그리고 visited배열에 집 번호를 넣어줌으로써 방문했음을 표시해준다. 그리고 문제에서 총 집의 수를 구해야 하기 때문에 homeCnt배열에 해당 집번호를 인덱스로 하는 원소값을 하나 증가시킨다.
그리고 큐에서 하나꺼내주면서 다음 좌표값을 구한다. 다음 좌표값은 상,하,좌,우를 돌면서 구하게 되는데, 이때 배열의 범위 안에 있는지 확인한다. 이를 만족하면 이 좌표값이 집인지 그리고 아직 방문하지 않았는지를 체크하고 만약 만족한다면 큐에다가 넣어주고 visited배열에 현재 집 번호를 넣어줌으로써 방문했음을 표시한다. 그리고 homeCnt에 해당 집번호를 인덱스로 하는 원소값을 하나 증가시킨다.
이렇게 모든 방향을 돌고 나면 map[current.i][current.j] 주변에 있는 집의 좌표가 큐에 대기중이다. 그러므로 큐에서 하나씩 꺼내준 좌표값을 기준으로 다시 주변에 집이 있는지를 탐색하고 큐에 넣기를 반복한다. 만약 이 모든 과정을 돌고 큐가 비게 되면 더 이상 주변에 집이 없으므로 while문을 종료하고 집 번호를 하나 증가시킨다.
그리고 다시 for문으로 돌아와 그 다음 집을 탐색하면서 위의 과정을 반복해주면 visited배열에 같은 집번호끼리 표시된 모습을 볼 수 있다.

코드

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 Boj_4963 {

	public static int w; // 너비
	public static int h; // 높이
	public static int[][] map;
	public static int[][] visited;
	static StringTokenizer st;
	public static Queue<Land> queue;
	public static int[] di = { -1, -1, 0, 1, 1, 1, 0, -1 }; // 상->시계방향
	public static int[] dj = { 0, 1, 1, 1, 0, -1, -1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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];
			visited = new int[h][w];
			
			StringTokenizer st;
			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());
				}
			}

			queue = new LinkedList<Land>();

			int landNum = 1; // 섬 번호
			for (int i = 0; i < h; i++) { //출발
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 1 && visited[i][j] == 0) {
						queue.offer(new Land(i, j));
						visited[i][j] = landNum;

						while (!queue.isEmpty()) {
							Land current = queue.poll();
							for (int dir = 0; dir < di.length; dir++) {
								int nx = current.i + di[dir];
								int ny = current.j + dj[dir];
								if (nx >= 0 && nx < h && ny >= 0 && ny < w) { //범위 안이고
									if(map[nx][ny] == 1 && visited[nx][ny] == 0) { //섬이고 아직 방문안했다면
										visited[nx][ny] = landNum;
										queue.offer(new Land(nx, ny));
									}
								}
							}
						}
						landNum++;
					}
				}
			}
			System.out.println(landNum-1);
		}
	}

	static class Land {
		int i, j;

		public Land(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
}