백준 4963번 : 섬의 개수 java

이 문제는 dfs를 이용하여 연결되어 있는 땅들을 확인하여 섬의 개수를 세는 문제입니다.

이 문제를 푸는 과정을 그림을 통해 보여드리도록 하겠습니다.

아래의 그림은 문제에 나와있는 예시입니다.

이제 이 그림에서 섬이 몇 개가 있는지를 찾아보겠습니다.

우선 초록색으로 표시된 땅 주변에 연결된 땅들을 찾아서 하나의 섬으로 묶어보겠습니다.

위의 그림과 같은 순서로 섬 하나가 만들어졌습니다.

이제 연결된 땅이 없으므로 떨어져 있는 섬들을 찾아보겠습니다.

노란색으로 표시된 땅 근처에도 연결된 땅이 없기 때문에 섬 하나가 또 완성되었습니다.

파란색으로 표시된 땅 주변의 땅들을 탐색해보도록 하겠습니다.

이제 더 이상 탐색하지 않은 땅이 없습니다.

따라서 이 지도에서 섬의 개수는 3개입니다.

이제 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static int row, col;
    static int[][] rowCol;
    static boolean[][] visited;
    static int[] dr = {1, 1, 1, -1, -1, -1, 0, 0};
    static int[] dc = {-1, 0, 1, -1, 0, 1, 1, -1};

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

        while (true) {
            int cnt = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());

            col = Integer.parseInt(st.nextToken());
            row = Integer.parseInt(st.nextToken());

            if (col == 0 && row == 0)
                break;

            rowCol = new int[row][col];
            visited = new boolean[row][col];

            for(int i = 0; i<row; i++){
                st = new StringTokenizer(br.readLine());

                for(int j = 0; j<col; j++)
                    rowCol[i][j] = Integer.parseInt(st.nextToken());
            }

            for(int i = 0; i<row; i++)
                for(int j = 0; j<col; j++)
                    if(rowCol[i][j] == 1 && !visited[i][j]){
                        search(i, j);
                        cnt++;
                    }

            sb.append(cnt).append("\n");
        }

        System.out.print(sb);
    }

    static void search(int r, int c){
        visited[r][c] = true;

        for(int i = 0; i<8; i++){
            int dR = r + dr[i];
            int dC = c + dc[i];

            if(dR<0||dC<0||dR>=row||dC>=col)
                continue;

            if(rowCol[dR][dC] == 1 && !visited[dR][dC])
                search(dR, dC);
        }
    }
}