[백준 / JS ] 13549 숨바꼭질3

Problem | 1446 지름길

🕊 난이도

골드5

📣 풀이 방법

1. bfs를 이용하여 최단 거리를 구한다.

   이 때 중요한 것은 큐 대신 덱을 이용하는 것이다. 그 이유는 2배 갈 수 있는 것은 0 초가 걸리기 때문에 먼저 탐색이 되어야 하기 때문이다.

📄 전체 풀이

const inputs = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [n, k] = inputs[0].split(" ").map(Number);

const bfs = () => {
  const q = [[n, 0]];
  const visited = new Array(100001).fill(false);
  visited[n] = true;

  while (q.length) {
    const [location, time] = q.shift();

    if (location === k) {
      console.log(time);
      return;
    }

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

      if (next === location * 2) {
        q.unshift([next, time]);
      } else {
        q.push([next, time + 1]);
      }
      visited[next] = true;
    }
  }
};

bfs();