[백준] 16953. A → B

정수 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

---

import java.util.Scanner;

public class Main {
    static int A;
    static int B;
    static int min;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        A = scanner.nextInt();
        B = scanner.nextInt();
        min = Integer.MAX_VALUE;
        bfs(A, 1);
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
    public static void bfs(double result, int count) {
        if(result > B) {
            return;
        }
        if(result == B) {
            min = Math.min(count, min);
            return;
        }
        bfs(result * 2, count + 1);
        bfs(result * 10 + 1, count + 1);
    }
}

재귀함수를 이용해 현재 값에 * 2를 한 값과 오른쪽에 1을 붙인 값을 다시 bfs함수로 넣어 모든 경우의 수를 탐색한다