문제

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.

각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

Image1.jpg

만약 위와 같다면 섬의 개수는 5개입니다.

입력
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.

두 번째 줄부터 격자판 정보가 주어진다.

코드

public class Island {
    static int[][] arr, check;
    static int[][] dir = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
    static int input1, answer = 0;
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        input1 = in.nextInt();
        arr = new int[input1+1][input1+1];
        check = new int[input1+1][input1+1];
        for(int i=1; i<=input1; i++){
            for(int j=1; j<=input1; j++){
                arr[i][j] = in.nextInt();
            }
        }
        solution(1,1);
        System.out.println(answer);
    }
    public static void solution(int x, int y){
        for(int i=1; i<=input1; i++){
            for(int j=1; j<=input1; j++){
                if(arr[i][j] != 0 && check[i][j] != 1){
                    dfs(i,j);
                    answer++;
                }
            }
        }
    }
    public static void dfs(int x, int y){
        if(arr[x][y] == 0 || check[x][y] == 1)return;
        check[x][y] = 1;
        for(int[] direct : dir){
            int nx = x+direct[0];
            int ny = y+direct[1];
            if(nx>0 && nx<=input1 && ny>0 && ny<=input1){
                dfs(nx, ny);
                check[nx][ny] = 1;
            }
        }
    }
}

설명

아일랜드 (BFS)

전에 풀었던 동일한 아일랜드 문제이다. 강의를 보니 DFS로도 풀수 있다고 해서 DFS로 풀어봤다. 문제를 처음 봤을 때도 DFS로 풀지 BFS로 풀어야할지 고민했었는데 그 생각이 맞았었나보다. 그래도 다행히 BFS로 풀어봐서 문제를 이해한 상태로 풀어서 그런지 DFS도 금방 풀었다.

DFS에서 중요한 부분은 check[][] 배열을 언제 체크해주냐에 따라 정답이 달라지므로 디버그를 찍어보면서 이해하는게 좋을거 같다!