[Algorithm] ➡️백준 16953 A ➡️ B

0. 문제

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

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

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

1. 아이디어

💡 BFS
💡 큐를 이용하여 두 가지 연산을 했을 경우, B와 작거나 같은 수를 큐에 넣음
💡 큐에서 나온 숫자가 B와 같다면 그 숫자를 return 함
💡 큐에 있는 숫자가 모두 나왔는데도 B와 같아진 수가 없다면, return -1

2. 핵심 풀이

1. 큐를 이용하여 두 가지 연산을 했을 경우, B와 작거나 같은 수를 큐에 넣음

if(cur.num*2 <= B) {
	q.add(new Cal(cur.num*2, cur.cnt+1));
}
if(cur.num*10+1 <= B) {
	q.add(new Cal(cur.num*10+1, cur.cnt+1));
}

2. 큐에서 나온 숫자가 B와 같다면 그 숫자를 return 함

if(cur.num == B) 
	return cur.cnt+1;

3. 큐에 있는 숫자가 모두 나왔는데도 B와 같아진 수가 없다면, return -1

while(!q.isEmpty()){
...
}

return -1;

3. 코드

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

public class Bruteforce_8 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		long A = Long.parseLong(s[0]);
		long B = Long.parseLong(s[1]);
		
		System.out.println(bfs(A,B));
	}

	static int bfs(long A, long B) {
		Queue<Cal> q = new LinkedList<>();
		q.add(new Cal(A,0));
		
		while(!q.isEmpty()) {
			Cal cur = q.poll();
			
			if(cur.num == B) 
				return cur.cnt+1;
			
			if(cur.num*2 <= B) {
				q.add(new Cal(cur.num*2, cur.cnt+1));
			}
			if(cur.num*10+1 <= B) {
				q.add(new Cal(cur.num*10+1, cur.cnt+1));
			}
		}
		
		return -1;
	}
	
	static class Cal{
		long num;
		int cnt;
		Cal(long num, int cnt){
			this.num = num;
			this.cnt = cnt;
		}
	}
}

4. 결과

성공✨
long을 안 써서 2번이나 틀렸다..😥