[백준] 2638번 - 치즈 (Gold 3)

문제 링크

백준 2638번 - 치즈 (Gold 3)

문제 설명

N x M 크기의 모눈종이 위에 치즈가 놓여있다.
외부 공기와 두 변 이상이 접촉한 칸의 치즈는 한 시간만에 녹아버린다.
단, 치즈 내부에 있는 공기와 접촉하는 것은 관계없으며 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다.
이 때 치즈가 모두 녹는데 걸리는 시간을 구하시오.

정답 코드 및 설명

문제를 풀기 위해서 필요한 것을 나열해보자.

1. 외부 공기가 있는 칸을 구해야 한다.
2. 각 치즈가 외부 공기와 접촉하는 변의 개수를 구해야 한다.
3. 한 시간이 지나 치즈가 녹은 후의 치즈 상태를 구해야 한다.

1 ~ 3을 성공적으로 구현했다면, 이를 반복해서 치즈가 모두 녹아 없어질 때까지의 시간을 구할 수 있다.

1번부터 생각해보자.
이 문제에서는 모눈종이의 맨 가장자리가 공기라는 조건이 있으므로, 맨 가장자리부터 BFS를 시작하면 외부 공기가 있는 칸을 알아낼 수 있다. 내부 공기와 외부 공기를 구분하기 위해, 처음에는 모든 공기 칸을 내부 공기로 설정하였다가 BFS로 체크되는 공기 칸을 외부 공기로 바꾸는 방식을 택했다.

2번은 위에서 BFS를 수행할 때 외부 공기 칸과 접촉한 치즈 칸이 있다면, 해당 치즈 칸에 저장된 외부 공기와 접촉하는 변의 개수를 1 늘려주면 된다. BFS에서 각 칸은 한 번씩만 지나게 되므로 중복으로 체크되거나 누락되는 일은 없다.

3번은 위에서 구한 치즈가 한 시간 후에 녹는 치즈라면, 치즈를 내부 공기로 바꿔주면 된다. 외부 공기인지는 1번으로 다시 돌아가서 확인하게 되므로 굳이 여기서 체크할 필요가 없다.

이를 코드로 구현하면 아래와 같다.
1번과 2번 과정은 코드의 43행 ~ 60행에서 한번에 수행하였으며, 3번 과정은 코드의 74행 ~ 78행에 해당한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2638 {
    static final int[][] NEXT = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static final int OUTSIDE = -2, INSIDE = -1;
    int n, m, numOfCheese;
    int[][] cheese;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        numOfCheese = 0;
        cheese = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                int curr = Integer.parseInt(st.nextToken());
                if (curr == 0) cheese[i][j] = INSIDE;
                if (curr == 1) {
                    cheese[i][j] = 0;
                    numOfCheese++;
                }
            }
        }
        setCheese();
    }

    void initializeCheese() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (cheese[i][j] > 0) cheese[i][j] = 0;
            }
        }
    }

    void setCheese() {
        boolean[][] isChecked = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        cheese[0][0] = OUTSIDE;
        isChecked[0][0] = true;
        initializeCheese();
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextI = curr[0] + NEXT[i][0];
                int nextJ = curr[1] + NEXT[i][1];
                if (!isValid(nextI, nextJ)) continue;
                if (cheese[nextI][nextJ] >= 0) cheese[nextI][nextJ]++;
                else if (!isChecked[nextI][nextJ]) {
                    isChecked[nextI][nextJ] = true;
                    cheese[nextI][nextJ] = OUTSIDE;
                    queue.add(new int[]{nextI, nextJ});
                }
            }
        }
    }

    boolean isValid(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < m;
    }

    int time() {
        int time = 0;
        while (numOfCheese > 0) {
            time++;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (cheese[i][j] < 2) continue;
                    cheese[i][j] = INSIDE;
                    numOfCheese--;
                }
            }
            setCheese();
        }
        return time;
    }

    void solution() throws IOException {
        input();
        System.out.println(time());
    }

    public static void main(String[] args) throws IOException {
        new BOJ2638().solution();
    }
}