[BOJ] 16953 :: A → B (JAVA)

문제출처 : BOJ 16953

---

문제 요약

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

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

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

---

풀이방법

타깃이 되는 정수 B 부터 거꾸로 A를 만든다고 생각해보자.
취할 수 있는 행동은 두가지 이다.

• 1) 2로 나눈다. ( 2로 나눠지고, 나눈 수가 A보다 같거나 클 때)
• 2) 1을 뺀 수를 10으로 나눈다. ( B-1 을 10으로 나눈 나머지가 0이고, 나눈 수가 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;
        }
    }

}

---