boj 2573 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

먼저 빙산 주위에 바다가 있는 위치 수만큼 빙산이 녹습니다.

 

이중for문으로 이거를 확인해주시면 되고, 주위에 바다가 있을 때마다 cnt[i][j]를 1씩 늘려줍니다.

그 다음 이중for문을 다시 돌려서 cnt[i][j]만큼 빙산을 녹여줍니다.

 

빙산을 녹이는 과정에서 빙산이 두 덩어리 이상으로 분리가 되면 그 시간을 출력해주시면 됩니다.

이 과정을 bfs로 구현하였습니다. 이중for문을 돌면서 방문안된 빙산을 발견하면 bfs를 호출하는데

만약 두 번째로 bfs에 들어가게 되면 빙산이 분리가 되었다는 말이 되기때문에 바로 시간을 출력해주시면 됩니다.

 

저는 문제를 읽어보니 최초로 주어지는 입력에는 무조건 빙산이 한 덩어리라는 조건이 없어서

빙산이 두 덩어리 이상으로 분리가 되었는지 체크하는 bfs함수를 먼저 호출하였습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[300][300];
    static int cnt[][] = new int[300][300];
    static boolean visit[][] = new boolean[300][300];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static void init() {
        for (int i = 0; i < N; i++)
            Arrays.fill(visit[i], false);
    }
 
    static void bfs(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (visit[nx][ny] || list[nx][ny] == 0)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int t = 0;; t++) {
            boolean chk = false;
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (list[i][j] == 0 || visit[i][j])
                        continue;
                    if (chk) {
                        System.out.println(t);
                        return;
                    }
                    bfs(i, j);
                    chk = true;
                }
            }
 
            if (!chk) {
                System.out.println(0);
                return;
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (list[i][j] == 0)
                        continue;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + direct[k][0];
                        int ny = j + direct[k][1];
 
                        if (list[nx][ny] == 0)
                            cnt[i][j]++;
                    }
                }
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (list[i][j] == 0)
                        continue;
                    list[i][j] = list[i][j] >= cnt[i][j] ? list[i][j] - cnt[i][j] : 0;
                    cnt[i][j] = 0;
                }
            }
            
            init();
        }
    }
 
    static void input() throws Exception {
        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++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}