[백준 2573번] 빙산 :: 늦깎이 IT

[백준 2573번] 빙산 URL

1. 빙산을 녹일 때 주의할 점이 있다. 왼쪽위부터 오른쪽아래까지 map을 탐색하면서 빙산을 녹일 때, 임의의 한 빙산을 녹일 때, 인접한 부분에 바다(0)가 있다고해서 무조건 녹이면 안되고, 바다로 된 자리가 현재 시점에 바다가 된건지 이전 시점에 바다가 된건지 확인해야한다.

2. melt() 메소드를 보면, 같은 시간내에 바다가된 경우 curMelt라는 boolean 배열에 체크를 해준다.

3. 빙산을 한 회 녹였다면, BFS탐색을 시작해서 빙산이 두 덩어리 이상이 되는지 확인한다.

4. BFS 탐색 후에, 빙산이 두 덩어리가 안되었다면 map을 전체탐색하며 빙산이 모두 녹았는지 확인한다.

빙산이 모두 녹아버렸다면 0을 출력한다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
 
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solve();
    }
 
    public static void solve() {
 
        int time = 1;
 
        while (true) {
 
            int count = 0;
            visited = new boolean[N][M];
            melt();
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!visited[i][j] && map[i][j] > 0) {
                        bfs(i, j);
                        count += 1;
                    }
                }
            }
            if (count >= 2) {
                System.out.println(time);
                return;
            } else if (isEmpty()) {
                System.out.println(0);
                return;
            }
            time += 1;
        }
    }
 
    public static void bfs(int row, int col) {
 
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(row, col));
        visited[row][col] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
 
            for (int i = 0; i < 4; i++) {
 
                int nr = node.row + dirX[i];
                int nc = node.col + dirY[i];
 
                if (isBoundary(nr, nc) && map[nr][nc] > 0 && !visited[nr][nc]) {
                    q.offer(new Node(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
    }
 
    public static boolean isEmpty() {
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] > 0)
                    return false;
            }
        }
        return true;
    }
 
    public static void melt() {
 
        boolean[][] curMelt = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
 
            for (int j = 0; j < M; j++) {
 
                if (map[i][j] > 0) {
 
                    for (int k = 0; k < 4; k++) {
 
                        int nr = i + dirX[k];
                        int nc = j + dirY[k];
 
                        if (isBoundary(nr, nc) && map[nr][nc] == 0 && !curMelt[nr][nc]) {
                            map[i][j] -= 1;
                            if (map[i][j] == 0)
                                curMelt[i][j] = true;
                        }
                        if (map[i][j] < 0)
                            map[i][j] = 0;
                    }
                }
            }
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
}
 
class Node {
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}