[node.js] 백준 17836번: 공주님을 구해라!

🔍 17836번: 공주님을 구해라!

클릭해서 문제 전체 보기🔼

📖 풀이 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [nmt, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
const [n, m, t] = nmt.split(" ").map(Number);
const graph = [new Array(m + 1).fill(1)];
for (let i = 0; i < n; i++) {
  graph.push([1, ...input[i].split(" ").map(Number), 1]);
}
graph.push(new Array(m + 1).fill(1));

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
const queue = [];
let head = 0;

const bfs = () => {
  let minTime = Infinity;
  queue.push([1, 1, 0]);
  graph[1][1] = 1;

  while (queue.length > head) {
    const [y, x, time] = queue[head++];
    if (time >= t) {
      if (minTime <= t) return minTime;
      else return "Fail";
    }

    for (let d = 0; d < 4; d++) {
      const ny = y + dy[d];
      const nx = x + dx[d];

      if (ny == n && nx == m) return Math.min(minTime, time + 1);

      if (graph[ny][nx] == 1) continue;

      if (graph[ny][nx] == 2)
        minTime = time + 1 + Math.abs(n - ny) + Math.abs(m - nx);

      queue.push([ny, nx, time + 1]);
      graph[ny][nx] = 1;
    }
  }
  if (minTime <= t) return minTime;
  else return "Fail";
};

console.log(bfs());

📢 풀이 설명
많은 메모리 초과, 시간 초과, 틀렸습니다를 겪은 후 풀어낸 문제다. 2시간이 걸렸어요 😭

이 문제의 핵심 풀이법은 검을 먹은 후 최소 시간은 맨해튼 거리로 계산하기(bfs 돌지 않음 !)이다. 내가 푼 문제 풀이법은 다음과 같다.

1. 그래프 만들 때 테두리를 1로 감싸두기 (크기가 가로 & 세로 둘 다 2칸씩 커짐, index도 +1됨)
2. 검이 없다는 전제 하에 bfs로 그래프를 돌기. 이때 기본 최소 시간은 Infinity
3. 벽이 아닌 부분 지나면서 벽으로 표시 바꾸기 (visited 대신 사용, 0 -> 1으로 바꾸는 것)
4. 검을 발견하면 (지금까지 지나온 시간 + 1) + 맨해튼 거리로 공주에게까지 갈 수 있는 최소 시간 갱신
5. 다시 검이 없다는 전제 하에 공주에게 가기 위해 그래프 돌기.
6. 이때 시간이 t시간을 넘었을 경우 || 공주에게 가는 길이 막혀 도달할 수 없는 경우
   6-1. 갱신한 최소 시간이 t보다 작거나 같으면 최소 시간 반환
   6-2. 아니면 Fail 반환

내가 찾아낸 내가 틀렸던 이유들이다. 혹시 같은 이유로 실패중이시라면 참고하세요 😉

• 메모리 초과: 검을 먹기 전, 검을 먹은 후 둘 다 bfs를 돌며 최소 시간을 찾아냈기 때문. 검을 먹은 후에는 맨해튼 거리로 계산해야함 !

• 시간 초과: 메모리가 문제라고 해서 head++ 방식 대신 shift()를 사용했더니 시간초과가 발생했다.

• 틀렸습니다: 검 없이는 목표 시간을 넘기거나 공주에게 도달하지 못하더라도, 검을 먹은 후 벽을 뚫으면 가능할 수도 있음. 이 경우를 if-else로 처리해야함.