아이디어

• 입력을 받으며 0이 아닌 점 개수(cnt)를 세서 초기화한다.
• 0이 아닌 아무 점을 찾는다.
  • 이때 점을 찾을 수 없었다면 빙산이 모두 물이 잠긴 상태고, 그 이전까지는 모두 연결되었다는 뜻이므로 0을 출력하고 종료한다.
• 점을 찾았다면 그 점부터 그래프를 DFS로 탐색한다.
  • BFS도 상관 없는데 간단하니깐…
• DFS의 결과가 이후 찾은 정점들의 전체 개수가 된다.
• DFS로 찾은 정점 개수가 cnt와 같으면 모든 정점이 연결되어있다는 뜻이다. 만약 아니라면 여기서 종료한다.
• 결과값을 1 증가시키고, 규칙에 따라 빙산을 잠기게 한다.
  • 이때 빙산이 잠길 때마다 cnt를 1 감소해서 cnt를 갱신해준다.
  • 주의: 이 때 입력받았던 원래의 2차원 배열로 진행하면, 이전에 행이나 열을 0으로 바꾼 것을 그대로 읽어 값에 오류가 생긴다.
  • 따라서 임시 2차원 배열에다 복사해둔 뒤, 복사한 배열에서 계산하고 계산이 모두 끝나면 덮어씌우는 방식으로 구현해야 한다.
• 2번부터의 과정을 무한 반복한다.

코드

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

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static int N, M, ans, cnt;  // cnt: 0이 아닌 칸 개수
    static int[][] map, tmp;
    static boolean[][] visited;

    static int[] dy = { 1, 0, -1, 0 };
    static int[] dx = { 0, 1, 0, -1 };

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());

        map = new int[N][M];
        for (int y=0; y<N; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<M; x++) {
                map[y][x] = Integer.parseInt(tk.nextToken());
                if (map[y][x] > 0)
                    cnt++;
            }
        }
        tmp = new int[N][M];
        visited = new boolean[N][M];

        while (true) {
            clearVisited();
            int[] pos = findAnyNonzero();
            if (pos == null) {
                ans = 0;
                break;
            }
            if (cnt > dfs(pos[0], pos[1])) break;
            ans++;
            update();
        }

        System.out.println(ans);
    }

    static void clearVisited() {
        for (int y=0; y<N; y++)
            for (int x=0; x<M; x++)
                visited[y][x] = false;
    }

    static int[] findAnyNonzero() {
        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                if (map[y][x] != 0)
                    return new int[] {y, x};
            }
        }
        return null;
    }

    static int dfs(int y, int x) {
        if (!borderCheck(y, x) || visited[y][x] || map[y][x] == 0)
            return 0;
        visited[y][x] = true;
        int sum = 0;
        for (int i=0; i<4; i++)
            sum += dfs(y + dy[i], x + dx[i]);
        return 1 + sum;
    }

    static void update() {
        // tmp에 복사
        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                tmp[y][x] = map[y][x];
            }
        }

        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                if (map[y][x] == 0) continue;

                int zeroCnt = 0;
                for (int i=0; i<4; i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];
                    if (!borderCheck(ny, nx)) continue;
                    if (map[ny][nx] == 0) zeroCnt++;
                }
                tmp[y][x] -= zeroCnt;
                if (tmp[y][x] <= 0) {
                    tmp[y][x] = 0;
                    cnt--;  // 가라앉음
                }
            }
        }

        // 덮어쓰기
        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                map[y][x] = tmp[y][x];
            }
        }
    }

    static boolean borderCheck(int y, int x) {
        return y >= 0 && y < N && x >= 0 && x < M;
    }
}

메모리 및 시간

• 메모리: 28172 KB
• 시간: 568 ms

리뷰

• 앞서 말한 주의점만 조심한다면 크게 어렵지는 않은 문제다.
• 저번 구현 문제 때 피를 봐서 그런지 너무 많이 모듈화 한 것 같기도 하다.
• 수업 때도 그랬지만, 중간에 N과 M 오타내는 이슈가 있었다. 오타가 나도 잘 안 보인다는게 문제.