[node.js] 치즈 ( 백준 2636번)

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const graph = [];
let [N, M] = [0, 0];

rl.on("line", (line) => {
    if (!N) {
        [N, M] = line.split(" ").map(Number);
    } else {
        graph.push(line.split(" ").map(Number));
        if (graph.length === N) {
            main();
            process.exit();
        }
    }
});

const main = () => {
    let visited = [];
    const xMove = [0, 0, -1, 1];
    const yMove = [1, -1, 0, 0];

    const bfs = (y, x) => {
        const queue = [];
        queue.push({ y, x });

        for (let i = 0; i < N; i++) {
            visited[i] = new Array(M).fill(false);
        }
        visited[y][x] = true;

        for (let i = 0; i < 4; i++) {
            const nextY = y + yMove[i];
            const nextX = x + xMove[i];

            if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
                if (!visited[nextY][nextX] && graph[nextY][nextX]) {
                    visited[nextY][nextX] = true;
                }
            }
        }

        while (queue.length) {
            const cur = queue.shift();

            for (let i = 0; i < 4; i++) {
                const nextY = cur.y + yMove[i];
                const nextX = cur.x + xMove[i];

                if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
                    if (!visited[nextY][nextX] && !graph[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        queue.push({ y: nextY, x: nextX });

                        for (let j = 0; j < 4; j++) {
                            const aroundY = nextY + yMove[j];
                            const aroundX = nextX + xMove[j];

                            if (
                                0 <= aroundY &&
                                aroundY < N &&
                                0 <= aroundX &&
                                aroundX < M
                            ) {
                                if (
                                    !visited[aroundY][aroundX] &&
                                    graph[aroundY][aroundX]
                                ) {
                                    visited[aroundY][aroundX] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    };

    let time = 0;
    let curCheese = graph.flat().filter((el) => el === 1).length;
    let preCheese;

    while (curCheese) {
        time++;
        bfs(0, 0);
        preCheese = graph.flat().filter((el) => el === 1).length;

        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (graph[i][j] === 1 && visited[i][j] === true) {
                    graph[i][j]--;
                }
            }
        }

        curCheese = graph.flat().filter((el) => el === 1).length;
    }

    console.log(time);
    console.log(preCheese);
};

빙산 문제와 매우 유사하다. 오히려 빙산보다는 쉬웠던 거 같기도 하다. bfs이긴 한데, 생각해볼 부분이 어제랑 역이라는 점도 있다.
어제는 빙산을 돌면서, 빙산이 바다와 닿은 부분을 체크해야 했지만, 이번에는 공기와 닿은 치즈를 찾아야 했다.
그런데 치즈의 내부에 공기층이 있는 것은 공기 면적으로 포함을 하지 않는다는 점이 달랐다.
예컨대, 도넛 모양의 치즈가 있다고 치면 도넛 가장자리는 1시간 후 녹겠지만, 내부의 공기층과 닿은 치즈 부분은 녹지 않는다.
따라서 graph에서 0인 면적과 닿았다고 해서 반드시 녹는 것이 아니라는 점이 이 문제의 핵심이었다.

따라서 착안을 다르게 해야 하는데, 이 문제는 친절하게도 graph의 가장 바깥자리들은 모두 0으로 이루어져 있다는 점이다.
0으로 이루어져 있기 때문에 공기층은 0,0과 반드시 이어져 있다.
따라서 0,0을 시작점으로 bfs를 하면 모든 공기층 ( 치즈 내부의 공기층을 제외한 ) 부분을 알 수 있다.
이 공기층의 네 방면에 대해서 치즈인 부분을 찾아 방문을 체크해주면 된다.
그리고 이후 bfs가 끝난 다음에 한 꺼번에 지워주면 된다.

따라서 bfs를 돌고 나온 다음에 치즈를 지워주는 이중 for문을 만든 것이다.
다음, pre와 cur의 치즈 개수를 구한 다음에, 아직 치즈가 남아있으면 계속 bfs를 반복한다.
치즈가 없다면 time과 preCheese를 출력해주면 된다.