정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
2 162
5
4 42
-1
100 40021
5
이 문제는 BFS 알고리즘을 이용해서 쉽게 풀 수 있는 문제였다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
long A = Long.parseLong(str[0]);
long B = Long.parseLong(str[1]);
solution(A, B);
}
static void solution(long a, long target) {
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(a, 0));
while(!queue.isEmpty()) {
Pair p = queue.poll();
if(p.x==target){
System.out.println(p.cnt+1);
return;
}
for(int i=0; i<2; i++) {
long x = 0;
if(i==0) {
x = 2*p.x;
}
else {
x = 10*p.x + 1;
}
if(x<=target)
queue.add(new Pair(x, p.cnt+1));
}
}
System.out.println(-1);
}
static class Pair {
long x;
int cnt;
public Pair(long x, int cnt) {
this.x=x;
this.cnt=cnt;
}
}
}