[백준 4963] 섬의 개수 자바 (DFS)

문제

4963번: 섬의 개수

접근방식

정사각형으로 이루어져 있는 섬과 바다 지도가 주어졌을 때  섬의 개수를 세는 문제이다. 

입력 조건에서 가로, 세로, 대각선으로 연결되어있는 사각형은 걸어갈 수 있는 사각형, 즉 연결되어있는 섬이다. 

왼쪽부터 시계방향으로 대각선을 포함한 위치를 계산하기 위해 아래와 같이 x값, y값의 변화값을 배열에 넣어준다. 

static int[] dx = {-1,-1,0,1,1,1,0,-1};
static int[] dy = {0,1,1,1,0,-1,-1,-1};

 

현재값에서 탐색 가능한 위치(board값이 1)인 경우 현재 값을 0으로 바꿔주고 다시 그 값을 기준으로 탐색해준다. 경로만을 찾는 것이 아니라 총 섬의 개수를 체크해야하기 때문에 이 함수를 입력받은 너비 w, 높이 h 크기 내의 모든 좌표를 돌면서 탐색하면 된다. 

public static void DFS(int x,int y){
        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 < m && board[nx][ny]==1){
                board[nx][ny]=0;
                DFS(nx,ny);
            }
        }
 }

풀이

import java.util.*;

public class Main {

    static int[][] board;
    static int n;
    static int m;
    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 static void DFS(int x,int y){
        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 < m && board[nx][ny]==1){
                board[nx][ny]=0;
                DFS(nx,ny);
            }
        }
    }

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(true){
            m = scanner.nextInt();
            n = scanner.nextInt();
            if(m == 0 && n ==0) break;
            board = new int[n][m];
            answer = 0;

            for (int i = 0; i < n; i++) {
                for(int j=0;j<m;j++){
                    board[i][j] = scanner.nextInt();
                }
            }
            
            Solution();
            System.out.println(answer);
        }

    }
}