백준 1697 숨바꼭질

문제

제한 사항

입출력 예

풀이

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 dis = new Array(100001).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;
        // dis[next] = dis[cur] + 1;
        queue.push([next, time + 1]);
      }
    }
  }
};

console.log(solution(input));

• 인프런 강의에 비슷한 문제가 있는데, 거기선 dis배열을 만들어 값을 저장했지만 여기선 큐에 넣을 때 변수를 하나 더 추가하는 식으로 풀었다.
• 주석은 dis배열을 사용하는 방식이다.