2638 치즈 (자바스크립트)

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

=====

문제 풀이

치즈들이 모두 사라질때까지 녹이는 행위를 반복할 것이므로 우선 while의 종료 조건은 치즈의 전체 갯수가 0이 되는 시점이다.입력값을 받아오면서 1의 갯수를 카운트하여 전체 치즈 갯수를 구하고 한 번에 탐색시마다 녹여지는 치즈의 갯수를 빼준다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const gr = input.slice(1).map((s) => s.split(' ').map(Number));

let cnt = gr.reduce((acc, cur) => acc + cur.filter((v) => v === 1).length, 0);

let stage = 1;
while (true) {
    const meltedCount = bfs();
    cnt -= meltedCount;
    if (cnt === 0) {
        console.log(stage);
        break;
    }
    stage++;
}

0,0 부터 탐색을 시작하면서 외부에 있는 치즈를 찾아서 녹여줄 bfs 함수를 작성한다.

이 때 문제에 주어진 치즈가 녹여져야 할 조건은 외부 공기와 접촉한 면이 2개 이상이라는 것이다. 여기에서 주의할 점은 외부 공기와 내부 공기가 나뉜다는 점이다. 만약 치즈가 공기가 접촉 중인 것이 외부 공기 1, 내부 공기 1이라면 이는 공기 접촉면이 2개라도 외부 공기 2가 아니므로 녹여지지 않는다. 

따라서 bfs함수에서는 탐색을 진행하면서 방문 체크를 할 visited 그래프에 방문을 했던 곳이 0 이라면 외부 공기로 기록하고 근처 외부공기를 탐색하기 위해 큐에 넣어준다. 1이라면 녹여질 수 있는 치즈 후보군에 넣어둔다. 

const bfs = () => {
    const OUTTER = 2;
    const INNER = -1;
    const CHEESE = 0;
    const dx = [0, 0, -1, 1];
    const dy = [-1, 1, 0, 0];
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => INNER)
    );
    const q = [[0, 0]];
    visited[0][0] = OUTTER;
    const candidatesOfMeltedPosition = [];
    while (q.length) {
        const [x, y] = q.shift();
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] !== -1) continue;

            if (gr[nx][ny] === 0) {
                q.push([nx, ny]);
                visited[nx][ny] = OUTTER;
            } else {
                visited[nx][ny] = CHEESE;
                candidatesOfMeltedPosition.push([nx, ny]);
            }
        }
    }


};

큐의 다 비워졌다는 것은 접근 가능한 외부 공기에 모두 접촉했다는 것이고 외부 공기와 가장 밀접한 녹여질 수 있는 치즈 후보군을 다 찾았다는 것이다.

이제 치즈 후보군을 꺼내어보면서 이 후보군과 밀접한 사면 중 외부공기가 2 이상이라면 녹여주는 작업을 하면 된다.

let changedCheeseCount = 0;

for (const [x, y] of candidatesOfMeltedPosition) {
    let cnt = 0;
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (visited[nx][ny] === OUTTER) {
            cnt++;
        }
    }
    if (cnt >= 2) {
        changedCheeseCount++;
        gr[x][y] = 0;
    }
}
return changedCheeseCount;

 

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, m] = input[0].split(' ').map(Number);
const gr = input.slice(1).map((s) => s.split(' ').map(Number));

let cnt = gr.reduce((acc, cur) => acc + cur.filter((v) => v === 1).length, 0);

const bfs = () => {
    const OUTTER = 2;
    const INNER = -1;
    const CHEESE = 0;
    const dx = [0, 0, -1, 1];
    const dy = [-1, 1, 0, 0];
    const visited = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => INNER)
    );
    const q = [[0, 0]];
    visited[0][0] = OUTTER;
    const candidatesOfMeltedPosition = [];
    while (q.length) {
        const [x, y] = q.shift();
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] !== -1) continue;

            if (gr[nx][ny] === 0) {
                q.push([nx, ny]);
                visited[nx][ny] = OUTTER;
            } else {
                visited[nx][ny] = CHEESE;
                candidatesOfMeltedPosition.push([nx, ny]);
            }
        }
    }

let changedCheeseCount = 0;

for (const [x, y] of candidatesOfMeltedPosition) {
    let cnt = 0;
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (visited[nx][ny] === OUTTER) {
            cnt++;
        }
    }
    if (cnt >= 2) {
        changedCheeseCount++;
        gr[x][y] = 0;
    }
}
return changedCheeseCount;
};

let stage = 1;
while (true) {
    const meltedCount = bfs();
    cnt -= meltedCount;
    if (cnt === 0) {
        console.log(stage);
        break;
    }
    stage++;
}