[백준] 13549 숨바꼭질3 - JavaScript(NodeJS)

문제

13549번: 숨바꼭질 3

 

풀이

수빈이가 N의 위치로부터 동생의 위치 K까지 가는 가장 빠른 시간을 구해야 한다.
1초마다 위치 X로부터 X-1, X+1로 이동할 수 있고, 순간이동을 하면 0초 후 2X의 위치로 이동한다.

 

방법

최소 시간을 구해야 하는 문제로, BFS 알고리즘을 사용한다.

 

작업마다 소요되는 시간이 다르므로 다음 위치에 방문할 때 우선순위를 고려해야 한다.

수빈이가 동생 위치에 도달하면 재귀가 멈추므로, 0초가 걸리는 2X를 최우선적으로 처리한다.

 

큐에 우선순위를 추가로 고려하기 위해서 덱 자료구조를 사용해보자.

덱 자료구조는 Double Ended Queue의 줄임말로,

덱의 앞과 뒤에서 모두 자료를 넣고 빼줄 수 있다.

위의 그림을 보면 이해가 빠를 것이다.

 

 

자바스크립트에서는 덱을 구현할 때 동일하게 빈 배열을 선언하고

unshift, shift, push, pop 메서드를 사용한다.

 

우선순위가 높은 작업은 unshift 메서드로 배열 맨 앞에 넣어줄 것이다.

 

또한 이미 지나온 위치는 방문하지 않기 위해 방문배열에 기록하며 중복을 피한다.

 

코드는 다음과 같다.

 

코드

const sol = (input) => {
  const [N, K] = input.split(" ").map(Number);
  const visit = Array.from({ length: 100100 }, () => 0);

  function bfs(N) {
    const queue = [];
    queue.push([N, 0]);
    visit[N] = 1;
    while (queue.length) {
      const [cur, time] = queue.shift();
      if (cur === K) return time;
      for (next of [cur * 2, cur - 1, cur + 1]) {
        if (!visit[next] && next >= 0 && next <= 100000) {
          visit[next] = 1;
          if (next == cur * 2) {
            queue.unshift([next, time]); // 2X로 이동할 때는 시간을 증가시키지 않고, 우선순위를 반영하여 큐의 맨 앞에 넣어준다.
          } else {
            queue.push([next, time + 1]); // X-1, X+1로 이동할 때는 시간을 증가시키고, 큐에 순서대로 넣어준다.
          }
        }
      }
    }
  }
  return bfs(N);
};

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    console.log(sol(line));
  })
  .on("close", () => {
    process.exit();
  });