https://www.acmicpc.net/problem/2636
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
📌 작성한 코드
// 2636
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let total = 0;
const [N, M] = input.shift().split(" ").map(Number);
const board = input.map((str) => {
const temp = str.split(" ");
temp.forEach((val) => {
if (val === "1") total++;
});
return temp;
});
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const bfs = (a, b) => {
const visited = Array.from({ length: N }, () => new Array(M).fill(false));
let count = 0;
const air = [];
const cheese = [];
air.push([a, b]);
visited[a][b] = true;
let idx = 0;
while (air.length > idx) {
const [x, y] = air[idx++];
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (!visited[nx][ny] && board[nx][ny] === "0") {
air.push([nx, ny]);
visited[nx][ny] = true;
} else if (!visited[nx][ny] && board[nx][ny] === "1") {
cheese.push([nx, ny]);
visited[nx][ny] = true;
}
}
}
cheese.forEach(([x, y]) => {
board[x][y] = "0";
count++;
});
return count;
};
let answer = [];
let remain = total;
while (true) {
const count = bfs(0, 0);
if (count === 0) {
break;
}
answer.push(remain - count);
remain -= count;
}
console.log(answer.length);
console.log(answer.length === 1 ? total : answer[answer.length - 2]);
📌 설명
문제 풀이 방법
1. bfs를 이용하여 공기와 맞닿은 부분을 구하고, 해당 부분을 녹인다.
2. 더 이상 녹일 치즈가 없을 때 까지 반복한다.
BFS 구현시 주의사항
1. 치즈를 바로 녹여버리면 공기와 맞닿는 부분이 늘어나서 제대로 된 계산이 불가능해진다. -> 기록해두었다가 한번에 녹이기
2. 치즈를 기준으로 bfs를 돌리면 가장자리를 찾기 어렵다. -> 공기를 기준으로 돌리기
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 3 : 17135 - 캐슬 디펜스 (0) | 2024.04.30 |
|---|---|
| [JavaScript/DP] 백준 골드 4 : 2624 - 동전 바꿔주기 (0) | 2024.04.24 |
| [JavaScript] 백준 골드 5 : 20165 - 인내의 도미노 장인 호석 (2) | 2024.04.18 |
| [JavaScript/DP] 백준 골드 5 : 11058 - 크리보드 (0) | 2024.04.12 |
| [JavaScript/DP] 백준 골드 5 : 5557 - 1학년 (0) | 2024.04.11 |