[백준] 2573번 빙산

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   2차원 배열 형태로 빙산의 높이가 주어지며, 높이인 양의 정수와 바다를 의미하는 0으로 초기화되어 있다. 빙산의 높이는 일년마다 그 칸의 4방향(상하좌우)으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. (단, 0보다 작아지지 않는다.)  한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 문제이다.

   첫째 줄에는 행과 열인 N, M이 주어지고, 그 다음 N개의 줄에는 줄 M개씩의 빙산의 높이(or 0)이 주어진다. 모든 입력은 빈칸으로 구분된다. 제한 사항은 다음과 같다.

 

• 3 ≤ N, M ≤ 300
• 0 ≤ 빙산의 높이 ≤ 10
• 0 ≤ 빙산의 개수 ≤ 10,000
• 배열의 첫번째 행과 열, 마지막 행과 열은 항상 0으로 채워진다.
• 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 0을 출력한다.

 

 

---

접근 방식

   DFS의 개념을 이용해 문제를 해결하였다. 문제 해결 방법은 맵에서 빙산을 찾은 뒤 빙산에 대해 DFS를 수행하며 높이를 낮춰가는 것이다. 이때 맵에서 빙산을 찾는 횟수가 빙산의 덩어리를 의미하기 때문에 맵 전체에 대한 재탐색 진행 여부를 횟수에 따라 정하게 된다. 예제를 통해 자세히 알아보자.

 

 

   예제의 맵에서 가장 처음으로 찾을 수 있는 유효한 빙산은 (1, 1)좌표의 2이다. 해당 좌표에 대해 DFS 탐색을 진행하게 된다. (이때 탐색 범위가 맵을 벗어나거나 재방문하는 경우는 탐색을 진행하지 않는다.)

 

 

   탐색 순서는 시계방향으로 좌측부터 시작한다고 가정하자. 탐색 대상이 바다(높이가 0)인 경우 현재 위치의 빙산 높이를 줄인다.

 

   다음 탐색 방향은 우측으로 빙산이 위치하는 것을 알 수 있다. 처음 방문하는 인접한 빙산을 발견하는 경우 해당 빙산에 대해 DFS를 호출한다.

 

 

   좌측에 있던 빙산은 현재 바다가 되었다. 하지만 문제에서 빙산이 녹는 것은 1년을 주기로 하기 때문에 현재 탐색에서 만들어진 0에 대해 주변 빙산들이 영향을 받아서는 안 된다. 따라서 영향을 줄 수 있는 0인지에 대한 구분은 방문 여부를 통해 결정한다. 지금까지의 탐색에서도 알 수 있듯이 일반적인 바다는 방문 여부(파란색 표시)가 표시되지 않지만 탐색 과정에서 만들어진 바다는 방문 여부가 표시되어 있는 것을 알 수 있다. 이 점을 이용해 좌측에 0에 대해선 무시한다.

 

 

   다음은 위쪽을 탐색한다. 위쪽에는 바다가 위치하므로 현재 빙산의 높이가 영향을 받게 된다. (DFS를 호출하는 것은 항상 인접한 빙산에 대해서만 이다.)

 

 

   우측에는 빙산이 존재한다. 해당 빙산에 대해서도 DFS를 호출한다.

 

 

   이전 과정들을 반복해보자. 빙산에 대해 4방향 탐색을 완전히 마무리하고 인접한 빙산으로 넘어가는 것이 아니기 때문에 다음과 같은 형태가 나오게 된다. 현 시점부터 과저을 다시 살펴보자.

 

 

   현재 위치는 (3, 1)좌표이며 위쪽을 탐색할 차례이다. 탐색 대상은 빙산이므로 DFS를 호출하여 탐색을 진행한다.

 

 

   좌측은 바다이므로 영향을 받아 높이가 줄게되지만 위쪽에 0은 탐색 과정에서 만들어진 바다이다. 따라서 영향을 받지 않아 빙산의 높이가 줄지 않는다.

 

 

   우측에 바다에는 영향을 받으며, 아래쪽에 6은 이미 방문한 빙산이기 때문에 DFS를 호출하지 않는다. 따라서 현재 빙산의 높이는 다음과 같이 변하게 된다.

 

 

   현재 좌표에서의 4방향 탐색은 종료되었다. 호출되었던 DFS가 종료되며 이전 DFS로 돌아가게 된다. 남은 과정을 진행하다 보면 다음과 같은 위치에서 DFS가 호출된다.

 

 

  4방향 중 3방향으로 바다와 인접했기 때문에 높이가 3이 줄지만, 빙산의 높이는 0보다 작아질 수 없기 때문에 해당 좌표는 0으로 초기화된다.

 

 

   처음 발견한 (1, 1)좌표의 빙산에 대한 DFS 결과가 종료되면 다음과 같이 초기화된다. (1, 1) 다음 좌표들을 탐색해봐도 이미 방문한 빙산밖에 발견할 수 없어 DFS가 호출되진 않는다. (만약 방문하지 않은 빙산이 발견된 경우 빙산의 덩어리가 나누어진 것이다.) 이 과정에서 발견한 빙산의 덩어리는 1개이므로 종료 조건을 만족하지 못 한다. 따라서 방문 여부를 false로 초기화하고 맵 전체에 대해 다시 이전 과정들을 반복한다. (빙산이 녹아 만들어진 바다가 새로운 탐색에선 영향을 미치게 된다.)

 

 

   위의 과정들을 반복하며 빙산의 덩어리가 2개 이상인 경우에는 걸린 년 수를, 0개인 경우 빙산이 다 녹았기 때문에 나누어질 수 없어 0을 출력한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 백준2573번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;
    static int[][] map;
    static int N, M;
    //방문 여부 저장
    static boolean[][] visited;
    //4방향 탐색을 위한 정의
    static final int[] X = {-1, 1, 0, 0};
    static final int[] Y = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        N = Integer.parseInt(token.nextToken());
        M = Integer.parseInt(token.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            token = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++)
                map[i][j] = Integer.parseInt(token.nextToken());
        }

        int year = 0;

        while (true) {
            //빙산 덩어리 개수
            int count = 0;
            //방문 배열 초기화
            for (int i = 0; i < N; i++)
                Arrays.fill(visited[i], false);
            //맵에 대한 DFS 탐색 수행
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < M; x++) {
                    //빙산이면서 처음 방문하는 경우
                    if (map[y][x] != 0 && !visited[y][x]) {
                        DFS(x, y);
                        //빙산 덩어리 개수 증가 
                        count++;
                    }
                }
            }
            //빙산이 전부 녹음 : 0, 빙산이 두 개의 덩어리로 나뉨 : 2 
            if (count != 1) {
                //빙산이 전부 녹은 경우 0 출력
                if (count == 0)
                    year = 0;
                break;
            }
            //년수 증가
            year++;
        }

        System.out.println(year);
    }

    public static void DFS(int x, int y) {
        //방문 여부 초기화
        visited[y][x] = true;

        //4방향 탐색 진행
        for (int i = 0; i < 4; i++) {
            int nextX = x + X[i];
            int nextY = y + Y[i];
            //배열의 범위를 벗어난 경우
            if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue;
            //이미 방문했던 경우
            else if (visited[nextY][nextX]) continue;
            //바다인 경우 현재 위치의 빙산의 높이를 감소
            if (map[nextY][nextX] == 0) {
                //0보다 작아질 수 없음
                if (map[y][x] != 0)
                    map[y][x]--;
            } else {
                //빙산인 경우 DFS 탐색 진행
                DFS(nextX, nextY);
            }
        }
    }
}