[백준] 13913 숨바꼭질4 - JavaScript(NodeJS)

문제

13913번: 숨바꼭질 4

풀이

1697번: 숨바꼭질

1697번 문제의 연장선이다.

 

수빈이가 동생에게 도달하기까지의 최소 시간과 지나온 경로까지 구하면 된다.

방법은 BFS를 이용할 것인데, 지나온 경로를 추적하기 위해서 배열을 따로 선언한다.

 

주의할 점

문제에서 구할 것은 최단시간이므로
2에서 10까지 이동한다 할 때 2-4-5-10이 최단 시간 경로이며, 2-4-8-9-10, 2-3-4-5-10 등의 경우의 수를 제거해야 한다.

 

그러므로 위치 X에는 단 한 번 만의 방문이 가능하다.
방문여부를 확인하면서, 경로 배열에 다음 위치 X의 인덱스에 이전의 위치 값을 넣어준다.

 

그림으로 표현하면 다음과 같다.

 

 

BFS가 끝나면 위와 같이 도착 위치의 인덱스를 기준으로 역추적하면 된다.
이 때 인덱스를 역추적하면서 배열에 push 했다면, 마지막에는 reverse 메서드로 뒤집어주면 된다.

 

추가로
방문할 위치 X는 0<=X<=100,000를 만족해야 하며
같은 레벨의 트리(도달하기까지 동일한 시간이 소요되는 위치)를 지날 때는 소요된 시간이 동일하도록 코드로서 표현해야 한다.

 

코드는 다음과 같다.

 

코드

const sol = (input) => {
  const [N, K] = input.split(" ").map(Number);
  const path = Array.from({ length: 100100 }, () => 0);
  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) {
          path[next] = cur;
          visit[next] = 1;
          queue.push([next, time + 1]);
        }
      }
    }
  }

  const time = bfs(N);
  const order = [];
  order.push(K);
  let prev = path[K];
  for (let i = 0; i < time; i++) {
    order.push(prev);
    prev = path[prev];
  }
  const result = `${time}\n${order.reverse().join(" ")}`;
  return result;
};

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