백준 / 그래프 / 13549번 / 숨바꼭질 3 / JS

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 

5 17

예제 출력 1 

2

 

/* 숨바꼭질 3 */
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

// N: 수빈이의 위치, K: 동생의 위치
const [N, K] = input.shift().split(' ').map(Number);

function solution(N, K) {
  const visit = Array.from({ length: 1e5+1 }, () => false);
  const deque = [];

  // [처음 수진이의 위치 N, 처음 시간 0]
  deque.push([N, 0]);
  // 처음 수진이의 위치 방문처리
  visit[N] = true;

  while(deque.length > 0) {
    const [cur, time] = deque.shift();
    // 동생의 위치에 도달할 경우 return
    if(cur === K) {
      console.log(time);
      break;
    }

    for(next of [cur*2, cur-1, cur+1]) {
      // 범위를 넘지않고 범위 안에 존재할 경우
      if(!visit[next] && next >= 0 && next <= 1e5) {
        visit[next] = true;
        if(next === cur * 2) { // 순간이동시에는 시간이 걸리지 않음
          // 걸리는 시간의 최솟값을 구해야 하므로 2배 이동시가 우선순위가 더 높다
          // 따라서 맨 앞에 넣어준다
          deque.unshift([next, time]);
        }
        else { // 한칸씩 이동시에는 1초의 시간이 걸림
          deque.push([next, time + 1]);
        }
      }
    }
  }
}

solution(N, K);