섬나라 아일랜드(DFS)

N*N의 섬나라 아일랜드, 섬은 1, 바다는 0

섬은 상하좌우 + 대각선 8방향

섬이 몇개인지 구하는 문제, 그림은 섬이 5개

입력

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

 

기존에 상하좌우 dx,dy배열에 대각선을 넣고 dfs로 섬을 판단하는 문제

 

Solution 함수로 보드 전체를 2중 for문을 돌면서 바다가 아닌 땅이 나오면

DFS 함수로 그 섬의 주변에도 갈수 있는 땅이 나오는지 판단한다

Solution 함수에서 땅을 발견하면 카운트를 늘려주고 DFS 함수를 호출, DFS함수가 주변이 전부 바다일때 까지 돌고 

다시 Solution 함수로 돌아와서 이어서 for문을 도는 방식

 

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

솔루션 함수로 보드를 돌다 땅을 발견하면 카운트를 늘리고 발견한 땅을 바다로 바꿔서 DFS함수에서 더 돌지 않게 한 다음

그 땅의 인덱스부터 시작하는 DFS함수를 호출한다

 

public void DFS(int x, int y){
        for (int k = 0; k < 8; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1){
                board[nx][ny] = 0;
                DFS(nx,ny);
            }
        }
    }

DFS 함수는 Solution 함수에서 받은 인자의 주변을 돌면서 더 이상 땅이 없을 때까지 땅을 바다로 바꾸면서

계속 주변을 탐색한다

 

전체 코드

 

import java.util.*;

class Main {
    static int[][] board;

    //상하좌우 후 대각선 좌상단부터 우하단까지
    static int[] dx = {-1,0,1,0,-1,-1,1,1};
    static int[] dy = {0,1,0,-1,-1,1,1,-1};

    static  int res = 0, n;

    public void DFS(int x, int y){
        for (int k = 0; k < 8; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1){
                board[nx][ny] = 0;
                DFS(nx,ny);
            }
        }
    }

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


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