문제

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){
                    Queue<Xy> que = new LinkedList();
                    que.offer(new Xy(i, j));
                    bfs(que);
                    answer++;
                }
            }
        }
    }
    public static void bfs(Queue<Xy> que){
        while(!que.isEmpty()){
            Xy xy = que.poll();
            check[xy.x][xy.y] = 1;
            for(int[] direct : dir){
                int nx = xy.x+direct[0];
                int ny = xy.y+direct[1];
                if(nx>0&&nx<=input1&&ny>0&&ny<=input1){
                    if(arr[nx][ny] == 1 && check[nx][ny] == 0){
                        que.offer(new Xy(nx,ny));
                        check[nx][ny] = 1;
                    }
                }
            }
        }
    }
    public static class Xy{
        int x;
        int y;

        public Xy(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

설명

문제를 처음 접했을 때 이 문제를 BFS로 풀어야할지 DFS로 풀어야할지 고민부터 했었다. 하지만 그 전 문제에서 퍼져나가는 경우에는 BFS를 활용하는게 좋다는 것을 배웠으므로 BFS를 활용하여 문제를 풀 생각을 하였다. 먼저 입력받은 2차원 배열을 그대로 2차원 배열에 넣는다. 그리고 check[][]라는 2차원 배열을 하나 더 만들어 해당 좌표를 검사했는지도 함께 확인하는 배열로 만들어뒀다.

그 후 우리가 확인해야하는것은 섬의 개수이다. 그래서 bfs가 1번 실행될때마다 섬이 1개가 있다고 생각했다. 왜냐하면 bfs를 다 돌고 나오면 해당 좌표에 연결되어 있는 섬 좌표는 모두 체크하고 나오고 다시 반복문으로 돌아갔을 때는 check[][]에 의해서 다시 해당 좌표를 체크하지 않기 때문이다. 그리고 queue에 넣기 위해 Xy라는 class를 만들어서 que에 넣고 정보를 사용하였다. 그 이외에는 따로 설명할 건 없는것 같다.

1주일 휴가를 갔다온 뒤에 다시 풀어보는 문제여서 걱정했는데 다행히 문제를 금방 풀어낼 수 있어서 다행이였다. bfs의 개념과 dfs개념 그리고 문제를 읽고 적절하게 적용시키는 것을 많이 연습하자. 또한 알고리즘도 중요하지만 기본 개념도 다시 공부해가면서 꼭 정리해보자!