[백준] 4963. 섬의 개수 - 실버2

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

4963번: 섬의 개수

 

문제 요약

1은 땅, 0은 바다로 입력이 주어진다. 땅으로 이루어진 섬의 개수를 세는 프로그램을 작성해야 한다. 두 땅이 같은 섬에 있으려면 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다.

 

문제 해결 아이디어

dfs로 해결했다. visted 2차원 배열을 생성해 각 좌표마다 방문했는지를 체크해 주었고, 방문하지 않은 땅에 해당하는 좌표들에 한해서 dfs를 각각 수행했다. 

dfs는 방문할 수 있는, 즉 8방향으로 갈 수 있는 좌표들에 대해 방문 체크를 했다. 따라서 같은 섬에서의 방문이 끝나면 하나의 dfs가 끝나며, 다른 땅에 해당하는 좌표에 대해 또 다시 dfs를 반복한다.

 

완성된 코드

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

public class Main_BOJ_4963_섬의개수 {
	
	/*
	 * 124ms
	 */
	
	static int[][] map;
	static boolean[][] visited;
	static int w;
	static int h;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		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 boolean[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());
				}
			}

			int cnt = 0;

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 1 && !visited[i][j]) {
						dfs(i, j);
						cnt++;
					}
				}
			}
			sb.append(cnt).append("\n");
		}
		System.out.println(sb);
	}

	public static void dfs(int i, int j) {
		int[] dr = { -1, -1, -1, 0, 1, 1, 1, 0 };
		int[] dc = { -1, 0, 1, 1, 1, 0, -1, -1 };
		visited[i][j] = true;

		for (int p = 0; p < 8; p++) {
			int nr = i + dr[p];
			int nc = j + dc[p];

			if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
				if (map[nr][nc] == 1 && !visited[nr][nc]) {
					dfs(nr, nc);
				}
			}
		}
	}
}