[백준 4963번] 섬의 개수

문제 링크: 4963번 제목

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

 

map을 순회하면서 육지인 지역(map[i][j]==1)이고 방문하지 않은 지역(!visit[i][j])인 경우에 DFS를 수행한다. 한 번 시행되고 나면 해당 육지와 연결된 지역은 모두 visit[i][j]는 true이므로 재방문되지 않고, 이러한 조건을 이용해서 섬의 개수를 센다.

 

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

public class Main {
    static int[] drow = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dcol = {-1, 0, 1, 1, 1, 0, -1, -1}; // 좌상단부터 시계방향

    static void dfs(int[][] map, boolean[][] visit, int h, int w, int row, int col) {
        visit[row][col] = true;

        if (map[row][col] == 0) return;

        for (int d = 0; d < 8; d++) {
            int nrow = row + drow[d];
            int ncol = col + dcol[d];

            if (nrow<0||ncol<0||nrow>=h||ncol>=w||visit[nrow][ncol])
                continue;

            dfs(map, visit, h, w, nrow, ncol);
        }
    }

    static int findIsland(int[][] map, int h, int w) {
        boolean[][] visit = new boolean[h][w];
        int cnt = 0;

        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (map[i][j]==1 && !visit[i][j]) {
                    dfs(map, visit, h, w, i, j);
                    cnt++;
                }

        return cnt;
    }

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

        while (true) {
            int[] temp;
            temp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int w = temp[0];
            int h = temp[1];

            // EOF
            if (w==0 && h==0) break;

            int[][] map = new int[h][w];
            for (int i = 0; i < h; i++)
                map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            System.out.println(findIsland(map, h, w));
        }
    }
}