[ 백준 / BOJ 16953 ] A -> B ( JAVA / 자바 )

https://www.acmicpc.net/problem/16953

16953번: A → B

 

문제

---

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

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

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

 

입력

---

첫째 줄에 A, B (\( 1 \leq A < B \leq 10^{9} \))

 

출력

---

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

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_BOJ_16953_AtoB {
    static long A, B;
    static Set<Long> isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        A = Long.parseLong(stringTokenizer.nextToken());
        B = Long.parseLong(stringTokenizer.nextToken());

        isVisited = new HashSet<>();
        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[]{A, 0});
        isVisited.add(A);

        while(!queue.isEmpty()){
            long now = queue.peek()[0];
            long cnt = queue.peek()[1];
            queue.poll();

            if(now == B){
                System.out.println(cnt+1);
                return;
            }

            if(now * 2 <= B && !isVisited.contains(now*2)){
                isVisited.add(now*2);
                queue.add(new long[]{now*2, cnt+1});
            }
            
            if(now * 10 + 1 <= B && !isVisited.contains(now*10+1)){
                isVisited.add(now*10+1);
                queue.add(new long[]{now*10+1, cnt+1});
            }
        }
        
        System.out.println(-1);
    }
}