[백준16953_자바스크립트(javascript)] - A → B

🔴 문제

A → B

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [a, b] = fs.readFileSync(path).toString().trim().split(' ').map(Number);
const q = [[a, 1]];

let ans = -1;
while (q.length) {
  const [target, cnt] = q.shift();

  if (target === b) {
    ans = cnt;
    break;
  }

  if (target > b) continue;

  q.push([Number(target + '1'), cnt + 1]);
  q.push([target * 2, cnt + 1]);
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

정수 A에서 B로 가는 최단거리를 BFS로 구해주면 된다.
큐에는 시작값 a와 연산횟수 1을 넣어준다.
그 후 큐의 요소를 빼서 target과 cnt 로 구조분해할당한 뒤 현재 target이 목표 값 b와 같다면 ans값을 현재 시도 횟수로 업데이트 한 뒤 BFS 로직을 종료한다.
target이 목표 값 b보다 크다면 이후 탐색이 무의미 하므로 다음 반복을 수행한다.
두 조건에 걸리지 않는다면 가장 오른쪽에 1을 추가해서 큐에 넣고, 2를 곱해서 큐에 넣는다.
이 때 오른쪽에 1을 붙이는 것이 2를 곱하는 것 보다 더 큰 수로 빠르게 접근할 수 있으므로 1을 붙이는 것을 더 먼저 큐에 넣어준다. 아래와 같이 시간차이가 많이 난다.

🔵 Ref