백준 13913 숨바꼭질 4

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim();
const solution = (input) => {
  let arr = input.split(" ");
  const start = +arr.shift();
  const end = +arr.shift();
  const visited = new Array(100100).fill(0);
  const path = new Array(100001).fill(0);
  const bfs = (start) => {
    const queue = [];
    visited[start] = 1;
    queue.push([start, 0]);
    while (queue.length) {
      const [cur, time] = queue.shift();
      if (cur == end) return time;
      for (let next of [cur - 1, cur + 1, cur * 2]) {
        if (!visited[next] && next >= 0 && next <= 100000) {
          visited[next] = 1;
          path[next] = cur; // 경로에 이전 위치 값을 넣어줌
          queue.push([next, time + 1]);
        }
      }
    }
  };

  const time = bfs(start);
  const order = [end]; //17
  let prev = path[end]; //16
  for (let i = 0; i < time; i++) {
    order.push(prev);
    prev = path[prev]; // 8 4 5
  }
  return `${time}\n${order.reverse().join(" ")}`;
};

console.log(solution(input));

• 숨바꼭질 문제의 업그레이드 버전
• path 배열을 만들고 경로에 이전 값을 넣어주고 후에 추적할 때 사용한다.