정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
타깃이 되는 정수 B 부터 거꾸로 A를 만든다고 생각해보자.
취할 수 있는 행동은 두가지 이다.
각각의 경우의 수를 Queue에 집어넣으며 너비우선탐색을 시도하여 최적해를 구할 수 있다.
BFS는 최소도달비용임이 보장되는 알고리즘이기 때문이다. 다만 우선순위에 주의하여야 하는데, 2)번 행동이 GREEDY한 관점에서 우선순위가 높은 행동이기 때문에 2번 행동을 우선해서 Queue에 집어넣어주면 해결된다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BOJ16953_A2B { // 2를 곱하거나(2로 나누기) 오른쪽에 1을 더하는 연산 둘 중에 하나 골라야 함.(1을 빼고 10으로 나누기)
public static void main(String[] args) {
// 입력
Scanner sc = new Scanner(System.in);
int A = sc.nextInt(); int B = sc.nextInt();
sc.close();
// 연산
Queue<Node> q = new LinkedList<>();
boolean flag = false;
q.offer(new Node(B, 0));
while (!q.isEmpty() && q.peek().index >= A) {
Node curr = q.poll();
if (curr.index == A) {
System.out.println(curr.minCount+1);
flag=true;
break;
}
if ((curr.index - 1) % 10 == 0 &&(curr.index - 1) / 10 >= A) {
q.offer(new Node((curr.index - 1) / 10, curr.minCount + 1));
}
if (curr.index % 2 == 0 && curr.index / 2 >= A) {
q.offer(new Node(curr.index / 2, curr.minCount + 1));
}
}
if (!flag) {
System.out.println(-1);
}
}
private static class Node{
int index;
int minCount;
public Node(int index, int minCount) {
this.index=index;
this.minCount=minCount;
}
}
}