[백준] - 13549 숨바꼭질 3 (node.js)

문제링크

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, k] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map(Number);

let q = [[n, 0]];

let visited = new Array(100100).fill(0);
visited[n] = 1;
let result = 0;

while (q.length !== 0) {
  const [now, time] = q.shift();

  if (now === k) {
    result = time;
    break;
  }

  for (let next of [now * 2, now - 1, now + 1]) {
    if (next < 0 || next > 100000 || visited[next]) continue;

    if (next === now * 2) {
      q.unshift([next, time]); // 우선순위가 더 높아서 unshift
    } else {
      q.push([next, time + 1]);
    }
    visited[next] = 1;
  }
}

console.log(result);

시간이 0초 소요되는 순간이동(곱하기 2)의 우선순위를 우선으로 해주는 것을 생각하지 못해서 계속 시간초과에 걸렸다.....

그리고 요소가 중복이 되더라도 거기까지 가는 시간이 다르니까 다른 것으로 봐야한다고 생각해서 처음에는 visited를 따로 안했는데 다시 생각해보니 시간이 다르다면 어차피 최소 시간을 구하는 것이기 때문에 먼저 방문한(= 그 위치까지 가는 최소 시간) 것만 남겨두는 것이 맞다는 생각이 들어 수정했다.

확실히 골드 5만 되어도 까다로워지는 거 같다....