[백준]1697번 숨바꼭질 - JavaScript(NodeJS)

문제

1697번: 숨바꼭질

풀이

수빈이가 동생이 있는 위치에 도달하기까지 최소 시간을 구하는 문제이다.

 

X 위치의 수빈이는 1초마다 X-1, X+1, 2X 로 이동할 수 있다.

이 문제는 bfs로 쉽게 해결할 수 있다.

 

트리 계층도

 

주의할 점은 다음과 같다.

 

계산 속도 향상을 위해서 동일 위치를 수빈이가 다시 방문하지 않도록 해야 한다.

방문할 위치 V는 0<=V<=100,000를 만족한다.
위 그림과 같이 트리 계층도에서 같은 레벨의 트리를 지날 때는 소요된 시간이 동일해야 한다.

 

코드는 다음과 같다.

코드

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 - 1, cur + 1, cur * 2]) {
        if (!visit[next] && next >= 0 && next <= 100000) {
          visit[next] = 1;
          queue.push([next, time + 1]);
        }
      }
    }
  }
  return bfs(N);
};

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