[Inflearn] 자바 알고리즘 문제풀이 #08-13 13. 섬나라 아일랜드(DFS)

문제

설명

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

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

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

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

입력 

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

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

 

출력 

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

 

예시 입력 1 

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

예시 출력 1

5

 

 

 

 

내 풀이

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

class Point {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main8_13 {
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    static int n, L=1;
    static int[][] board, dis;
    static Queue<Point> Q = new LinkedList<>();

    public void BFS() {
        while(!Q.isEmpty()) {
            Point cur = Q.poll();
            if(board[cur.x][cur.y]==0) return;
            else {
                board[cur.x][cur.y]=0;
                dis[cur.x][cur.y]=L;
            }

            for (int i = 0; i < 8; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1) {
                    board[nx][ny]=0;
                    dis[nx][ny] = L;
                }
            }
            L++;
        }
    }

    public static void main(String[] args) {
        Main8_13 T = new Main8_13();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new int[n][n];
        dis = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.nextInt();
                if(board[i][j]==1) Q.offer(new Point(i, j));
            }
        }
        T.BFS();
        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer = Math.max(answer, dis[i][j]);
            }
        }
        System.out.println(answer);
    }
}

엉망인 코드입니다.... 도전 실패 !

미로의 최단거리 통로, 토마토 문제랑 비슷한 흐름으로

board[]에서 1 값을 가진 것들을 기반으로 1개의 섬을 세어줄 때마다 dis[]에 1씩 증가한 값을 넣고

(첫 번째 섬은 dis[]배열에서 1 값을, 두 번째 섬은 2 값을 갖는 식으로)

끝까지 반복하고 나서 dis에서 최대값을 찾으면 섬의 개수이지 않을까....라는 생각이었다.

 

 

 

선생님 풀이

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

class Point {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main8_13 {
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    static int n, answer=0;
    public void DFS(int x, int y, int[][] board) {
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1) {
                board[nx][ny]=0;
                DFS(nx, ny, board);
            }
        }
    }
    public void Solution(int[][] board) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j]==1) {
                    answer++;
                    board[i][j]=0;
                    DFS(i, j, board);
                }
            }

        }
    }

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

문제 해결이 흐름이 끊기지 않고 동시 다발적으로 뻗어나간다 => BFS

같은 작은 문제를 해결 하는 것을 반복한다 => DFS 

이런 느낌인 건가.,,?

아직 차이를 모르는 것이야... 적응이 안되는 것이야...

 

그래두 혼자 끙끙 해보고 강의 들으면 유레카 하는 것처럼 뇌가 번쩍 뜨이는 느낌이라 너무 좋다ㅠㅠㅠㅠ

간단하게 생각하고 확장하는 사고를 하자.......!  그래도 재미있었다 오늘두👊🏻 (졌잘싸.)

 

 

 

다음 시간에는 내가 시도한 방법인 BFS로도 푸니까 이 답답함을 해결할 수 있을 듯 !!

https://rookie-programmer.tistory.com/111

[Inflearn] 자바 알고리즘 문제풀이 #08-14 14. 섬나라 아일랜드(BFS)

전체적인 흐름을 제어하는 함수(solution)와 반복적인 작업만 수행하는 함수(BFS, DFS)를 분리하는 코드는 또 새로웠다.

다음에 응용할 수 있게 머리에 넣어놔야지 ㅎ,ㅎ

 

 

 

결과