아일랜드 (DFS)

최준호·2021년 10월 16일
0

알고리즘 강의

목록 보기
73/79

문제

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[][] 배열을 언제 체크해주냐에 따라 정답이 달라지므로 디버그를 찍어보면서 이해하는게 좋을거 같다!

profile
코딩을 깔끔하게 하고 싶어하는 초보 개발자 (편하게 글을 쓰기위해 반말체를 사용하고 있습니다! 양해 부탁드려요!) 현재 KakaoVX 근무중입니다!

0개의 댓글