알고리즘) 섬나라 아일랜드(DFS, BFS 활용)

문제

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

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

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

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

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

 

---

1) DFS 방식 풀이

🧐 접근 방식

 인접 행렬을 입력받으며 그 값이 1인 칸이 나올 경우 DFS를 통해 연속될 수 있는 한 재귀함수를 호출한다. 이 때 지나온 좌표는 check 해둔다. 시작 지점의 좌표가 체크해둔 좌표가 아닌 처음 만나는 좌표일 때 총 섬의 수를 증가시킨다.

🧐 개선 방식

 공간 효율성을 위해 체크하는 배열을 사용하지 않고, 인접 행렬에서 섬으로 확인한 좌표의 경우에 그 값을 1에서 0으로 변경시키는 방식을 선택했다. 이와 더불어서 인접 행렬의 배열도 인덱스가 곧 좌표가 될 필요가 없기 때문에 0부터 인접 행렬의 크기도 \( (n + 1) * (n + 1) \)에서 \( n * n \)로 변경했다.

초기 작성 코드

import java.util.Scanner;

// 섬나라 아일랜드
public class Main {
    static int n;
    static int[][] matrix;
    static boolean[][] checked;
    static int[] ym = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] xm = {0, 1, 1, 1, 0, -1, -1, -1};
    static int cnt= 0;

    void DFS() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (!checked[i][j] && matrix[i][j] == 1) {
                    checked[i][j] = true;
                    DFS(i, j);
                    cnt++;
                }
            }
        }
    }

    void DFS(int y, int x) {
        for (int i = 0; i < 8; i++) {
            int my = y + ym[i];
            int mx = x + xm[i];
            if (my > 0 && mx > 0 && my <= n && mx <= n) {
                if (!checked[my][mx] && matrix[my][mx] == 1) {
                    checked[my][mx] = true;
                    DFS(my, mx);
                }
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        matrix = new int[n + 1][n + 1];
        checked = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                main.DFS();
            }
        }

        System.out.println(cnt);
    }
}

 

개선 코드

import java.util.Scanner;

// 섬나라 아일랜드
public class Main {
    static int n;
    static int[][] matrix;
    static int[] ym = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] xm = {0, 1, 1, 1, 0, -1, -1, -1};
    static int cnt= 0;

    void DFS() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = 0;
                    DFS(i, j);
                    cnt++;
                }
            }
        }
    }

    void DFS(int y, int x) {
        for (int i = 0; i < 8; i++) {
            int my = y + ym[i];
            int mx = x + xm[i];
            if (my >= 0 && mx >= 0 && my < n && mx < n) {
                if (matrix[my][mx] == 1) {
                    matrix[my][mx] = 0;
                    DFS(my, mx);
                }
            }
        }
    }

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                main.DFS();
            }
        }

        System.out.println(cnt);
    }
}

 

2) BFS 방식 풀이

🧐 접근 방식

 DFS 방식으로 푸는 경우와 같게 인접행렬의 가로축, 세로축 인덱스를 바꿔가며 해당 좌표의 값이 1인 경우 8방위의 좌표를 살펴 이 값이 1일 때 Queue에 넣는 방식으로 해결한다. 한 번 BFS를 실행시킬 때마다 cnt값을 증가시킨다.

작성 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 섬나라 아일랜드(BFS 방식 풀이)
public class Main {
    static int n;
    static int[][] matrix;
    static int[] ym = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] xm = {0, 1, 1, 1, 0, -1, -1, -1};
    static int cnt= 0;
    static class Node {
        int y;
        int x;

        public Node (int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    void solution() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = 0;
                    BFS(i, j);
                    cnt++;
                }
            }
        }
    }

    void BFS(int row, int col) {
        Node root = new Node(row, col);
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            Node r = q.poll();
            for (int i = 0; i < 8; i++) {
                int y = r.y + ym[i];
                int x = r.x + xm[i];
                if (y >= 0 && y < n && x >= 0 && x < n && matrix[y][x] == 1) {
                    matrix[y][x] = 0;
                    q.offer(new Node(y, x));
                }
            }
        }
    }

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

        main.solution();
        System.out.println(cnt);
    }
}