백준 13549 숨바꼭질 3

문제

제한 사항

입출력 예

풀이

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 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;
        if (next === cur * 2) {
          queue.unshift([next, time]);
          // 시간이 적을 수록 앞에 있어야하니.
        }
        queue.push([next, time + 1]);
      }
    }
  }
};

console.log(solution(input));

• *2하는 경우가 시간이 추가되지 않는 것으로 바뀌었다.
• 시간이 늘어나지 않은 것을 먼저 처리해줘야 함으로 unshift를 이용해 큐의 가장 앞에 넣어줬다.