[백준 2636] 치즈
January 29, 2023
문제
https://www.acmicpc.net/problem/2636
아이디어
처음 생각에 바깥쪽 공기와 붙어있는 치즈는 녹아야 하고, 안쪽 구멍과 붙어있는 치즈는 녹지 않아야 하기 때문에 어떻게 바깥쪽 공기와 안쪽 구멍을 구분해야 하는지 헤맸는데 생각해보니 [0, 0] 좌표는 무조건 공기이기 때문에 시작점과 이어진 곳을 공기라고 인식하고, 바로 옆에 맞닿은 치즈만 제거하면 되는 거였다.
- 입력 값을 가지고 전체 맵을 나타내는 2차원 배열을 만든다.
-
더 이상 녹을 치즈가 없을 때까지 이하 로직을 반복한다.
- 큐에 [0, 0] 좌표를 넣는다.
-
큐가 비어있게 될 때까지, 꺼내면서 다음을 반복한다. (BFS 탐색)
- 현재 위치의 값이 0이면 공기이므로, 현재 위치의 상하좌우에 해당하는 위치를 큐에 넣는다.
- 현재 위치의 값이 1이면 치즈이므로, 녹이고 갯수를 기록한다.
- 진행 시간 카운트를 기록한다.
소스코드
// 입력 정제
const fs = require("fs");
function getInput(caseID) {
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/i${caseID}.txt`;
const input = fs.readFileSync(filePath).toString().split("\n").map(item => item.trim());
input.pop();
const [height, width] = input.shift().split(" ").map(item => Number(item));
const map = [];
for (let y = 0; y < height; y++) {
map.push(input.shift().split(" ").map(item => Number(item)));
}
return [height, width, map];
}
// 문제
const [height, width, map] = getInput(1);
function isInBoundary(x, y) {
if (x < 0 || x >= width) return false;
if (y < 0 || y >= height) return false;
return true;
}
function solution() {
const queue = [];
let hourCount = 0; // 한 시간 지날 때마다 카운트
let prevMeltCount = 0; // 모두 녹기 한 시간 전에 남아있는 치즈의 갯수
let meltCount = 0; // 현재 녹는 치즈의 갯수
// 한 시간 지날때마다 가장자리의 치즈가 녹는다.
do {
let visited = Array.from({length: height}, () => Array.from({length: width}, () => 0));
meltCount = 0;
queue.push([0, 0]);
while (queue.length > 0) {
const [nowY, nowX] = queue.shift();
if (isInBoundary(nowX, nowY) && !visited[nowY][nowX]) {
visited[nowY][nowX] = 1;
// 현재 위치가 공기이면 근처 노드 BFS 탐색
if (map[nowY][nowX] === 0) {
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
for (let i = 0; i < 4; i++) {
const nextX = nowX + dx[i];
const nextY = nowY + dy[i];
queue.push([nextY, nextX]);
}
// 현재 위치가 치즈이면 녹음
} else if (map[nowY][nowX] === 1) {
meltCount++;
map[nowY][nowX] = 0;
}
}
}
if (meltCount === 0) break;
hourCount++;
prevMeltCount = meltCount;
} while (meltCount > 0);
console.log(hourCount);
console.log(prevMeltCount);
}
// 실행
solution();