const fs = require("fs");
const stdin = (
process.platform === "linux"
? fs.readFileSync("/dev/stdin").toString()
: fs.readFileSync("../input.txt").toString()
).split("\n");
const input = (() => {
let line = 0;
return () => stdin[line++];
})();
const direction = [
[1, 0, 0],
[-1, 0, 0],
[0, 1, 0],
[0, -1, 0],
[0, 0, -1],
[0, 0, 1],
];
function bfs(l, g, L, R, C) {
g[l[0][0]][l[0][1]][[0][2]] = "#";
while (l.length) {
const [f, y, x, count] = l.shift();
for (const d of direction) {
const nx = x + d[0];
const ny = y + d[1];
const nf = f + d[2];
if (
nx >= 0 &&
nx < C &&
ny >= 0 &&
ny < R &&
nf >= 0 &&
nf < L &&
g[nf][ny][nx] !== "#"
) {
if (g[nf][ny][nx] === "E") return `Escaped in ${count + 1} minute(s).`;
g[nf][ny][nx] = "#";
l.push([nf, ny, nx, count + 1]);
}
}
}
return "Trapped!";
}
function findStart(graph, L, R, C) {
for (let l = 0; l < L; l++) {
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (graph[l][r][c] === "S") return [l, r, c, 0];
}
}
}
}
const answer = [];
while (true) {
const [L, R, C] = input()
.trim()
.split(" ")
.map((v) => Number(v));
if (L === 0) break;
const graph = [];
for (let i = 0; i < L; i++) {
const row = [];
for (let r = 0; r < R; r++) {
row.push(input().trim().split(""));
}
graph.push(row);
input();
}
answer.push(bfs([findStart(graph, L, R, C)], graph, L, R, C));
}
console.log(answer.join("\n"));
3차원 배열을 사용한 BFS 문제였습니다. 처음에 시간 초과가 발생했었는데 방문 처리를 현재 좌표일 경우에 해줘서 생긴 문제였습니다.
...
const [f, y, x, count] = l.shift();
g[f][y][x] = "#";
현재 좌표를 가지고 방문 처리를 해주는 방법으로는 다음 좌표를 체크할 때, 모든 경우를 체크해야 하므로 시간 초과가 나옵니다. 어차피 최소 시간이니 que에 다음 좌표를 넣을 때, 방문 처리 해버리면 됩니다.
for (const d of direction) {
const nx = x + d[0];
const ny = y + d[1];
const nf = f + d[2];
if (
nx >= 0 &&
nx < C &&
ny >= 0 &&
ny < R &&
nf >= 0 &&
nf < L &&
g[nf][ny][nx] !== "#"
) {
if (g[nf][ny][nx] === "E") return `Escaped in ${count + 1} minute(s).`;
g[nf][ny][nx] = "#";
l.push([nf, ny, nx, count + 1]);
}
}
코드에 대한 설명이 상세하고 이해하기 쉽네요. BFS에 대한 이해가 필요하다는 점과 해당 문제를 해결하는데 있어서 중요한 부분을 잘 강조해주신 것 같아요. 숙지하고 나면 문제를 풀 때 큰 도움이 될 것 같습니다. 좋은 정보 감사합니다.