[노드JS/알고리즘] 백준 - 16953번 A -> B (DFS 풀이)

- 문제

16953번: A → B

- 코드

let [A, B] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split(" ")
  .map((v) => +v);

let answer = -1;
const DFS = (A, B, cnt) => {
  if (A === B) {
    answer = cnt + 1;
    return;
  } else {
    if (A * 2 <= B) DFS(A * 2, B, cnt + 1);
    if (A * 10 + 1 <= B) DFS(A * 10 + 1, B, cnt + 1);
  }
};

DFS(A, B, 0);
console.log(answer);

 

그리디로 풀 수 있지만, DFS로 풀어보았다.

 

 

가능한 연산 두 가지에 맞게 재귀를 호출하였다. 

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

하지만, 무작정 두 가지 경우를 재귀로 돌리면 스택 오버플로우가 발생할 수 있으므로

A에서 2를 곱하였을 때, B보다 작거나 같다면 2를 곱하고,

A에 1을 가장 오른쪽에 추가하였을 때, B보다 작거나 같다면, 1을 수의 가장 오른쪽에 추가한다.

 

재귀가 끝나는 조건은 문제에서 나왔듯이 A와 B가 같아지는 경우이다. 

그리고 출력 조건이 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값이기 때문에 answer = cnt+1을 하고 리턴.