[BOJ - JAVA] 2573 - 빙산 (DFS)

# 주소

https://www.acmicpc.net/problem/2573

2573번: 빙산

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main {
    static int n, m;
    static int dx[] = {1, 0, 0, -1};
    static int dy[] = {0, 1, -1, 0};
    static boolean[][] visit;
    static int arr[][];
    static int melt[][];
    static int count = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        melt = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        int year = 0;
        while (true) {
            count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (visit[i][j] == false && arr[i][j] != 0) {
                        dfs(i, j);
                        count++;
                    }
                }
            }
            if (count == 0) {
                System.out.println(0);
                break;
            } else if (count >= 2) {
                System.out.println(year);
                break;
            }
            melt();
            year++;
        }
    }
    public static void dfs(int x, int y){
        visit[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                continue;
            }
            if(arr[nx][ny] == 0){
                melt[x][y]++;
            }
            if(visit[nx][ny] == false && arr[nx][ny] != 0){
                dfs(nx,ny);
            }
        }
    }
    public static void melt(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = arr[i][j] - melt[i][j];
                if(arr[i][j] < 0){
                    arr[i][j] = 0;
                }
                visit[i][j] = false;
                melt[i][j] = 0;
            }
        }
    }
}

DFS 문제 중 가장 난이도가 있었습니다.

지금까지 DFS의 넓이를 구하거나 이동 경로의 횟수를 구하는 문제가 주를 이루었지만 이번 "빙산"의 문제는 DFS의 넓이가 2가 되었을 때, 그떄의 연차를 구하는 것이기 때문에 생각할 부분이 많았습니다.

그리고 arr와 melt 배열 2가지를 이용해서 문제를 풀어야 하는데 한 번 살펴보겠습니다.

arr를 일단 제일 먼저 입력받습니다.

그리고 정답이 될 year를 0으로 초기화 합니다.

이후 while문을 계속 돌릴 것이므로 while(true)로 정한 뒤 내부르 들어갑니다.

count = 0으로 계속 초기화를 해주셔야 합니다. 안그러면 count가 셀 수 없이 증가합니다..

예를들어 1년차 때 빙산이 한 덩어리, 2년차 때 빙산이 두 덩어리 되었으면 count가 3이 되어버리기 때문입니다.

이후 이중 for문에서, visit이 false이고 arr[i][j] 가 0이 아닌 곳에 대해 dfs문을 실행하는데 한 번 dfs가 실행되면 count가 증가합니다.

따라서 정답이 되려면 이 count가 2가 되었을 때를 출력하면 되겠습니다.

여기서 만약 count가 0이면 그냥 0을 출력하고 종료하고 2보다 커지면(2덩어리 이상이면) year를 출력합니다.

그리고 melt메서드를 실행합니다.

이 melt() 메서드는 빙산이 녹을떄의 과정입니다.

0년차 -> 1년차가 되었을 때 빙산이 

0년차

에서

이 되어야 하듯이 1년차를 나타내려면 빙산의 어디 부분이 녹을지를 연산해주어야 합니다.

이 melt는 그럼 주변의 인근한 지점에 대해 arr에서 뺀 값이면 되겠지요?

그럼 이 arr에서 뺄 melt배열은 어떻게 구할 수 있을까요?

그 구문은 dfs내부에서 확인할 수 있습니다.

dfs문을 먼저 살펴봅시다.

    public static void dfs(int x, int y){
        visit[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                continue;
            }
            if(arr[nx][ny] == 0){
                melt[x][y]++;
            }
            if(visit[nx][ny] == false && arr[nx][ny] != 0){
                dfs(nx,ny);
            }
        }
    }

dfs내부는 제일 먼저 방문했는지 여부를 나타내는 visit을 true로 바꾸어 주며 시작합니다.

그리고 nx와 ny에 대해 for문으로 상하좌우를 나타냅니다.

또한 nx,ny,nx,ny가 지정된 범위를 만족하면 continue를 해주고 만약 새로 이동한 nx,ny의 arr값이 0이라면 melt값을 증가시킵니다.

그렇게 되면 melt값이 모두 구해지겠지요??

그리고 arr값이 0이 아닌 육지의 위치라면 dfs(nx,ny)를 실행하여 계속해서 가능한 인덱스를 탐색합니다.

최종적으로 이 dfs함수가 모두 실행되고 나면 melt는 바다의 위치에 대해서도 값을 가집니다.

이유는 dfs를 쭉 실행하면서 인근에 있는 arr가 0이면 항상 melt를 ++시켜주었기 떄문에 melt는 모든 인덱스에 대해 값을 가집니다.

하지만 우리가 구하는 것은 육지의 위치에서 바다에 가라앉는지 여부를 확인하는 것이잖아요?

따라서 melt메서드의 조건을 붙여주어야겠습니다.

melt에서 만약 arr에서 melt를 뺐을 때 해당 arr가 음수가 되면 그냥 arr를 모두 0으로 바꾸어 버리면 어떨까요?

그리고 0보다 크거나 같으면 그대로 가는 것이지요.

그렇게 하고 melt와 visit을 초기화 시키면 다음 while문을 실행할 때 (년차가 올라갔을 때) 다시 초기화된 visit과 melt를 가지고 dfs문을 실행할 수 있는 것이지요.

arr는 그대로 melt를 빼고 남은 상태에서요.

이해가 가셨나요?

따라서 대게의 경우 melt()메서드와 year를 dfs를 실행하기 전에 넣어야 하는 것 아니냐고 반문하실 수 있겠지만 잘 생각해보면 0년차의 경우부터 구하는 것이므로 이것들을 뒤에 두는 것이 맞습니다.

만약 1년차부터 시작하고 싶을 경우엔 저것들을 앞에 두어도 되겠습니다만 0년차의 경우부터 2개의 빙산으로 쪼개지는 일도 존재할 수 있기 떄문에 뒤에 두는 것이 맞습니다.

감사합니다.