섬나라 아일랜드(DFS)

문제설명

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

입력 설명

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

출력 설명

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

입력예제

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

출력예제

5

---

내 코드

import java.util.Scanner;

public class Main_8_13 {
    static int n;
    static int answer = 0;
    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; // 출발지점을 0으로 초기화하기 위해
                    dfs(i, j, board);// i, j는 board에서 1인 좌표
                }
            }
        }

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

    }
}

• DFS를 활용하여 풀어보았다.
• 이전 문제들은 동서남북 방향만 살펴보면 되었지만 이번 문제는 대각선까지 포함되므로 8 방향을 살펴보기 위해static int[] dx = {-1,-1,0,1,1,1,0,-1};
static int[] dy = {0,1,1,1,0,-1,-1,-1};처럼 초기화 하였다.
• solution(int[][] board)함수를 이용하여 중첩 for문을 통해 2차원 배열인 board를 확인하여 만약 해당 칸이 1이라면 answer++를 해주고 시작지점도(board[i][j]) 0으로 초기화 해준다.
• dfs(int x, int y, int[][] board)를 통해 현재 칸 기준으로 8 방향 중 1이 있다면 해당 칸으로 이동하고 다시 돌아가지 못하게 0으로 초기화 시켜주는 함수이다.

알게된 점

• DFS를 사용할 때 무조건 if와 else를 사용하는 줄 알고있었다. 이 문제를 통해 DFS라도 if와 else를 꼭 전부 사용할 필요가 없다는 것을 알게되었다.