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

A → B

 

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

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

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

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

16953번: A → B

---

---

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16953_AtoB {
	static long A, B;
	static boolean visit[];
	static long answer;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken()); // target
		answer = 0;
		bfs();
		System.out.println(answer+1);
	}
	
	public static void bfs() {
		Queue<Long> Q = new LinkedList<>();
		Q.add(A);
		
		while(!Q.isEmpty()) {
			int size = Q.size();
			
			for(int s= 0; s<size; s++) {
				long cur = Q.poll();
				if(cur>B) continue;
				if(cur==B) return;
				Q.add(cur*2);
				Q.add(cur*10+1);
			}
			answer++;
		}
		answer = -2;
	}

}