[백준] 16953 A → B Node.js (DFS/BFS 풀이)

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

---

문제풀이

✅ 답안 #1 : DFS - 재귀함수로 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().split(' ').map(Number);
let answer = -1; // 디폴트값 -1

const dfs = (start, goal, cnt) => {
  if (start === goal) answer = cnt + 1;
  else {
    if (start * 2 <= goal) {
      dfs(start * 2, goal, cnt + 1);
    }
    if (Number(start + '1') <= goal) {
      dfs(Number(start + '1'), goal, cnt + 1);
    }
  }
};

dfs(N, K, 0);
console.log(answer);

✅ 답안 #2 : BFS - Queue로 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().split(' ').map(Number);

const bfs = () => {
  const queue = [N, 1];

  while (queue.length) {
    const cur = queue.shift();
    const cnt = queue.shift();

    if (cur === K) return cnt;
    else {
      if (cur * 2 <= K) {
        queue.push(cur * 2, cnt + 1);
      }
      if (Number(cur + '1') <= K) {
        queue.push(Number(cur + '1'), cnt + 1);
      }
    }
  }
  return -1;
};

console.log(bfs());