[백준 2573] 빙산(Java)

문제 링크 : https://www.acmicpc.net/problem/2573

이 문제는 dfs와 문제의 로직을 잘 구현하면 풀 수 있습니다.

문제의 로직은 다음과 같습니다.

1. while(true) 반복문을 돈다.
2. 현재의 빙산 개수를 체크한다.
3. 만약 빙산 개수가 2 이상이라면 break 후 결과를 출력한다.
4. 빙산이 다 녹을 때까지 분리되지 않으면 break 후 0을 출력한다.
5. 주위의 0의 수만큼 빙산 수를 줄인다.

여기서 주의할 점은 4번과 5번입니다. 4번의 경우 이중 for문을 또 만들어 진행하기보다는 처음에 빙산을 입력받을 때 remain 변수에 빙산 수를 저장하고, 빙산이 없어질때마다 remain-- 하여 remain==0일 경우를 찾아 출력하시면 됩니다. 5번의 경우는 만약 이중 for문을 돌릴 때 그때그때 빙산을 줄인다면 늦게 녹는 빙하는 주위에 0이 더 많아져 잘못된 결과가 발생합니다. 따라서 배열에 녹을 수치를 미리 저장한 후 이후 해당값만큼 빼주면 되겠습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    static int N,M;
    static int[][] req = new int[301][301];
    static boolean[][] check;
    static int[][] meltedIceberg = new int[301][301];
    static int cnt;
    static int remain = 0;
    static int res = 0;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static void meltIceberg(int y, int x){
        int num = 0;
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || ny>=N || nx<0 || nx>=M) continue;

            // 빙산의 수만큼 num++
            if(req[ny][nx] == 0) num++;
        }

        meltedIceberg[y][x] = num;
    }

    // dfs로 빙산 개수 세기
    static void checkSameIceberg(int y, int x){
        check[y][x] = true;

        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || ny>=N || nx<0 || nx>=M) continue;

            // 0은 빙산이 아니므로 제외
            if(!check[ny][nx] && req[ny][nx] != 0){
                checkSameIceberg(ny,nx);
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                req[i][j] = Integer.parseInt(st.nextToken());
                if(req[i][j]!=0) remain++;
            }
        }

        int idx = 0;
        while(true){
            // 현재 빙산의 개수 체크
            check = new boolean[301][301];
            cnt = 0;
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(!check[i][j] && req[i][j] != 0){
                        checkSameIceberg(i,j);
                        cnt++;
                    }
                }
            }

            // 만약 빙산의 개수가 2 이상이라면 res = cnt
            if(cnt>=2){
                res = idx;
                break;
            }

            // 빙산이 다 녹을때까지 분리되지 않으면 그대로 종료
            if(remain==0) break;

            // 주위의 0의 수만큼 빙산 수 줄이기
            // 이때 빙산이 동시에 녹지 않아 늦게 녹는 빙하는 주위에 0이 더 많아져 잘못된 결과 발생하므로 배열에 데이터 저장
            meltedIceberg = new int[301][301];
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(req[i][j] != 0) meltIceberg(i,j);
                }
            }

            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(req[i][j] != 0){
                        req[i][j] -= meltedIceberg[i][j];
                        if(req[i][j]<=0){
                            req[i][j] = 0;
                            remain--;
                        }
                    }
                }
            }
            idx++;
        }
        System.out.println(res);
    }
}