[백준] 4963번 : 섬의 개수 - JAVA [자바]

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

dfs 알고리즘 문제이다.

1. 섬을 배열에 입력 받는다.
2. 0,0 부터 땅을 탐색하면서 아직 방문하지 않았으며 땅이 있으면 방문한다.
3. 방문한 땅과 같은 섬인 다른 땅을 탐색한다.
   3.1 갈 수 있는 땅은 상하좌우 대각선들에 있는 땅이다.
   3.2 상하좌우 대각선들에 있는 땅을 탐색하는 방법은
   int[] xMove = {0, 0, -1, 1, 1, 1, -1, -1};
int[] yMove = {-1, 1, 0, 0, 1, -1, 1, -1}; 배열이다.
   3.3 현재 x, y에 xMove[0], yMove[0] 을 더해주면 현재 x, y의 한칸 아래에 있는 칸이다.
   3.4 이런식으로 0부터 8까지 더하면 x, y의 상하좌우 대각선들에 있는 땅의 위치를 알 수 있다.
4. 아직 방문하지 않았으며 현재 땅에서 갈 수 있는 땅이라면 이동하여 방문 처리 해주고 이동한 땅에서 또 이동 할 수 있는 땅이 있는지 확인하며 섬 하나를 만든다.
5. 위의 과정을 반복하면서 섬의 갯수를 구하여 출력한다.

public class bj4963 {

    public static int w, h, count;
    public static boolean[][] land;
    public static boolean[][] visited;
    static int[] xMove = {0, 0, -1, 1, 1, 1, -1, -1};
    static int[] yMove = {-1, 1, 0, 0, 1, -1, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            String[] split = br.readLine().split(" ");
            w = Integer.parseInt(split[0]);
            h = Integer.parseInt(split[1]);
            if (w == 0) break;

            visited = new boolean[h][w];
            land = new boolean[h][w];
            count = 0;
            for (int i = 0; i < h; i++) {
                String[] split1 = br.readLine().split(" ");
                for (int j = 0; j < w; j++) {
                    int num = Integer.parseInt(split1[j]);
                    if (num == 1) {
                        land[i][j] = true;
                    } else land[i][j] = false;
                }
            }

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // 땅이며 아직 방문하지 않은 땅이면 탐색 시작
                    if (land[i][j] && !visited[i][j]) {
                        dfs(i, j);
                        count++;
                    }
                }
            }


            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int x, int y) {
        // 방문 처리
        visited[x][y] = true;

        // 나의 상하좌우 대각선 다 살피기
        for (int i = 0; i < 8; i++) {
            int newX = x + xMove[i];
            int newY = y + yMove[i];
            // 주어진 칸 안에 있는 곳 일때
            if (newX >= 0 && newX < h) {
                if (newY >= 0 && newY < w) {
                    // 탐색하는 칸이 땅이며 아직 방문하지 않은 곳이라면
                    if (land[newX][newY] && !visited[newX][newY]) {
                        dfs(newX, newY);
                    }
                }
            }
        }
    }
}