BOJ 4963번 섬의개수

 

오늘의 주제

오늘의 주제는 BOJ 4963번 섬의개수 입니다.  문제는 아래와 같습니다.

 

이 문제를 보고 첫번째로 "연결된 섬을 찾기 위한 탐색하기", 두번째로 "탐색을 지속적으로 이루어가면서 섬이 아닌 위치, 이미 방문을 했던 위치는 건너뛰고 탐색"을 진행하면 될 것 이라 생각했습니다.

 

제가 작성한 코드는 다음과 같습니다.

public class boj_4963 {

    static int[][] result;
    static int[][] arr;
    static int row;
    static int col;
    static int cnt;
    
    // 상하좌우, 대각선 4방향
    static int[] dx = {0,0,1,-1,-1,-1,1,1};
    static int[] dy = {1,-1,0,0,-1,1,-1,1};
    
    public static void main(String arg[]) {
        Scanner sc = new Scanner(System.in);
        while(true) {

            col = sc.nextInt();
            row = sc.nextInt();
            cnt = 0;

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

            result = new int[row][col];
            arr = new int[row][col];

            for(int i=0; i < row; ++i) {
                for(int j=0; j< col; ++j) {
                    arr[i][j] = sc.nextInt();
                }
            }

            for(int i=0; i < row; ++i) {
                for(int j=0; j < col; ++j) {
                    if(arr[i][j] == 0 || result[i][j] == 1) continue;
                    else {
                        dfs(arr, i, j, result);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

    public static void dfs(int[][] arr, int r, int c, int[][] result) {

        if(r >= row || c >= col || r < 0 || c < 0) return;
        if(arr[r][c] == 0 || result[r][c] == 1 ) return;

        result[r][c] = 1;

        for(int i : dx) {
            for(int j : dy) {
                dfs(arr, i, j, result);
            }
        }
    }
}