정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
2 162
5
2 → 4 → 8 → 81 → 162
4 42
-1
100 40021
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());