[인프런/DFS/섬나라 아일랜드]

<<풀이>>

import java.util.Scanner;

class Main {
    static  int answer = 0, n;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1 ,-1, -1};

    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) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = in.nextInt();
            }

        }
        T.solution(arr);
        System.out.println(answer);

    }
}

 

이 문제는 DFS 문제 중에서도 쉬운 문제에 속한다.

 

이 문제의 핵심은 DFS이다.

 

외부에 참조해서 들어오는 예를 들어 board 같은 경우는 실제 board 값도 변경이 된다. (참조하는 거는 그대로이다. 변수만 여러개 생기는 것이다.)

 

나는 복사 본 배열 (모두 0으로 된)을 만들어서 1이 있으면 1로 변경을 시키고, 다음 과정에서 기존 배열은 1인데 복사본도 1이면 넘어가고 기존 배열은 1이고 복사본은 0이면 answer++ 해서 답을 구하는 구조를 생각했다.

 

하지만 강사님은 기존 배열 board 값을 0으로 변경을 시켜가며 answer++ 해줬다. 

 

결과적으로는 강사님의 풀이 방식이 훨씬 리소스 등 여러부분에서 효율적이라고 볼 수 있다.

 

오늘도 좋은 걸 배웠다.

 

---

오랜만에 풀어보니 뇌가 오랜만에 자극이 온것 마냥 ㅋㅋ 개운 했다 ㅋㅋ 그래도 어떻게 할지 방향성 코드 짜는 형식은 기억이 잘 나는 것 같다

 

꾸준히 매주 1-2개씩 풀어나가면서 자료구조에 대한 이해도를 더욱 강화 시켜나가자