[인프런] 08_13 섬나라 아일랜드(DFS)

📖  문제

---

문제설명

• N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
• 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.
• 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

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

입력설명

• 첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
• 두 번째 줄부터 격자판 정보가 주어진다.

출력설명

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

출력 예시

⚠️  주의사항

---

• 4방향이 아닌 8방향 체크
• 1개라도 있으면 섬으로 간주

✍️  이해

---

/**
 * 이전에 풀었던 DFS 문제와 비슷한 방법
 * 대각선도 체크해야 하므로 4방향이 아닌 8방향 체크
 * 1이 혼자 있어도 섬이므로 1확인하는 순간 출력값 누적
 *
 * 1. 이동 할 방향 배열 2개 생성 (8 방향)
 * 2. 입력값들 정의
 * 3. 배열 돌면서 1인 경우 answer 누적 후 DFS 호출해서 8방향 1값 확인
 * 4. 지나간 곳은 0으로 초기화
 * 5. answer 출력
 */

✏️  풀이

---

import java.util.Scanner;

public 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) {
        board[x][y] = 0;
        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++;
                    DFS(i, j, board);
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();

        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);
    }
}

---