[백준][자바(java)][dfs] #4963 섬의 개수

<문제>

4963번: 섬의 개수

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

[입력]

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

[출력]

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

---

<풀이 과정>

섬에서 섬으로 이동할 때, 가로, 세로, 대각선으로 이동이 가능함으로 한 섬의 기준으로 8개의 방향으로 이동할 수 있게된다. 

위 그림을 보면 기준이 되는 섬이 A[i][j]라면 A[i+1][j-1]은 왼쪽위대각선, A[i][j+1]은 오른쪽, A[i-1][j]는 아래임을 볼 수 있다. 이를 이용하기 위해 다음과 같은 배열을 이용할 것이다.

static int[] col = {0, 0, -1, 1, -1, 1, -1, 1};
static int[] row = {1, -1, 0 , 0 ,1, 1, -1, -1};

또한, 입력받은 int[][] island 배열을 이용하여 연결되어있는 섬으로 이동 할 수 있다.

위 그림을 보면 기준 섬에서 연결되어있는 섬은 오른쪽아래 섬 하나임을 알 수 있다.

그렇다면 오른쪽 아래 섬으로만 이동할 수 있다. 

그리고 int[][] visit 배열을 이용하여 방문하지 않은 섬에 대해서만 이동할 수 있도록 해줄 것이다.

만약 첫번째 칸부터 이동을 시작하면 기준섬으로 이동했다고 해보자. 기준 섬에서 연결되어있는 섬은 위, 아래 섬이지만, 위의 섬의 경우 이미 방문한 섬이기 때문에 이동할 수 없어 아래 섬으로만 이동할 수 있을 것이다.

 

이 모든 것을 반영하여 코드를 작성하면 다음과 같다.

---

import java.util.Scanner;
 
public class Main {    
    static int w, h;
    static int[][] island;
    static int[][] visit;
    static int[] col = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[] row = {1, -1, 0 , 0 ,1, 1, -1, -1};
    //위, 아래, 왼, 오, 왼위대(왼쪽 위 대각선), 오위대, 왼아대, 오아대
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while(true) {
            w = sc.nextInt();
            h = sc.nextInt();
            
            island = new int[h][w];
            visit = new int[h][w];
            
            int result = 0;
            
            if(w == 0 && h == 0) 
                break;
            
            
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    island[i][j] = sc.nextInt();
                }
            }
            
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    if(visit[i][j] == 0 && island[i][j] == 1) {
                        dfs(i, j);
                        result++;
                    }
                }
            }
            
            System.out.println(result);
        }
    }
    
    static void dfs(int x, int y)
    {
        visit[x][y] = 1;
        
        for (int i = 0; i < 8; i++) {
            int next_row = x + row[i];
            int next_col = y + col[i];
            
            if(next_row < 0 || next_row >= h || next_col < 0 || next_col >= w) {
                continue;
            }
            if(island[next_row][next_col] == 1 && visit[next_row][next_col] == 0) {
                dfs(next_row, next_col);
            }
        }
    }
}
 

---

<참고 자료>
velog, [백준] 4963 - 섬의 개수 (java), https://velog.io/@hammii/%EB%B0%B1%EC%A4%80-4963-%EC%84%AC%EC%9D%98-%EA%B0%9C%EC%88%98-java