[boj] 1697. 숨바꼭질 (node.js)

문제 요약

[boj] 1697. 숨바꼭질 (node.js)

• 주어진 두 지점 간 이동방법이 3가지로 정해져 있을 때, 시작점부터 도착점에 도달 가능한 최단 시간은?

풀이

• 1초에 const getCand = (node) => [node - 1, node + 1, node * 2]; 이 세 가지의 후보 중 하나로 이동 가능하다. 따라서 이를 함수로 만들어 활용했고, BFS로 time[] 배열에 값을 갱신하여 queue에 입력하는 노드가 도착 노드인 경우 바로 return 해 주었다.
• 점의 위치가 0 ≤ N ≤ 100,000 으로 고정되어 있음을 유의하고 불필요한 지점을 +-무한대로 탐색하는 일을 방지해 주어야 한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++].split(" ").map(Number);
const getCand = (node) => [node - 1, node + 1, node * 2];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  let [node, fin] = input();
  let queue = [node];
  console.log(bfs());
  process.exit();

  function bfs() {
    if (node == fin) return 0;
    let time = [];
    let visited = [];
    time[node] = 0;
    visited[node] = 1;
    while (queue.length) {
      node = queue.shift();
      const cand = getCand(node);
      for (let i = 0; i < 3; i++) {
        const elem = cand[i];
        if (visited[elem] || elem < 0 || elem > 100000) continue;
        visited[elem] = 1;
        time[elem] = time[node] + 1;
        if (elem == fin) return time[fin];
        queue.push(elem);
      }
    }
  }
});

주절주절

• 처음에 최대숫자의 자릿수를 잘못 보고 조건에 0을 하나 더 붙이고 풀어, 불필요한 탐색이 일어나 시간초과가 계속 발생했다. 숫자 제대로 확인하자!