[Algorithm] 섬나라 아일랜드(DFS, BFS)

설명

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

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

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

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

 

입력

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

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

 

출력

첫 번째 줄에 섬의 개수를 출력한다.

 

 

 

풀이 과정.

BFS와 DFS둘다 같은 방식으로 해결했다.

전체탐색으로 한 좌표씩 탐색하면서 1이 걸리면 섬갯수+1 해주고 그 좌표의 상하좌우대각선 전부 확인하여 1로 이어진 부분은 0으로 처리하고 나간다. 그리고 전체탐색을 이어서 진행한다. (반복)

 

 

 

풀이.

DFS방식

public class Main {
    static class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static int n;
    static int[][] board;
    static int[] dx = {-1, 1, 0, 0, -1, 1,1,-1};
    static int[] dy = {0, 0, -1, 1, 1, -1,1,-1};

    static void DFS(Point point){
        for (int i = 0; i < 8; i++) {
            int nx = point.x + dx[i];
            int ny = point.y + dy[i];
            if (nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= n - 1 && board[nx][ny] == 1) {
                board[nx][ny] = 0;
                DFS(new Point(nx, ny));
            }
        }
    }

    static void Solution(){
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == 1){
                    board[i][j] = 0;
                    DFS(new Point(i,j));
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        Solution();
    }
}

BFS방식

public class Main{
    static class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static int n;
    static int[][] board;
    static int[][] ch;
    static int[] dx = {-1, 1, 0, 0, -1, 1,1,-1};
    static int[] dy = {0, 0, -1, 1, 1, -1,1,-1};
    static Queue<Point> Q = new LinkedList<>();
    static int result = 0;

    static void BFS(int x, int y){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <n; j++) {
                if(board[i][j] == 1){
                    Q.offer(new Point(i,j));
                    result++;
                }
                while(!Q.isEmpty()){
                    Point temp = Q.poll();
                    for (int k = 0; k < 8; k++) {
                        int nx = temp.x + dx[k];
                        int ny = temp.y + dy[k];
                        if(nx>=0 && nx<=n-1 && ny>=0 && ny<=n-1 && board[nx][ny] == 1){
                            Q.offer(new Point(nx, ny));
                            board[nx][ny] = 0;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        BFS(0, 0);
        System.out.println(result);
    }
}

 

 

---

 

정리 :

상하좌우, 네방향 대각선

int [ ] dx = { -1, 1, 0, 0, -1, 1,1,-1 };
int [ ] dy = { 0, 0, -1, 1, 1, -1,1,-1 };

좌표는 Point class하나 만들어서 사용하는게 편한 것 같다.