[백준] 16953 - A → B (JAVA)

문제

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

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

입력

첫째 줄에 A, B ($1 ≤ A < B ≤ 10^9$)가 주어진다.

출력

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

---

풀이

BFS를 이용하여 최소 연산 횟수를 찾는 문제이다. 주의할 것은 B의 최댓값이 $10^9$이므로, 오버플로우가 일어날 수 있다는 것이다.

첫 번째 연산인 $num \times 2$일 때는 int의 최댓값인 $2^{31}-1$을 초과하지 않지만, 두 번째 연산에서는 오버플로우가 일어날 수 있으므로 64bit 자료형인 long을 사용하거나, unsigned int를 사용해야 한다. 하지만 자바에서는 unsigned int를 자료형으로 지원하지 않으므로 long을 사용해야 한다.

자연스럽게 visited를 사용해서 중복체크를 해주었는데, 다른 분들의 코드를 보니 이 문제에서는 visited가 없어도 시간 초과가 일어나지 않는 듯하다. 그래도 일단 설명을 해보자면, visited를 여타 다른 문제처럼 배열을 이용해서 사용한다면 최대 $10^9$의 크기의 배열이 필요하게 된다. 그렇기에 map을 사용하여 visited 체크를 해주면 된다.

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    static int

    static long mul(long n) {
        return n*2L;
    }
    static long add_right(long n) {
        return n * 10L + 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bf.readLine());

        long A = Integer.parseInt(stk.nextToken());
        long B = Integer.parseInt(stk.nextToken());

        Deque<Long[]> deque = new ArrayDeque<>();
        Long[] value = { A, 1L };
        deque.add(value);

        Map<Long, Boolean> visited = new HashMap<>();

        while(!deque.isEmpty()) {
            value = deque.removeFirst();

            if(value[0] == B) {
                System.out.println(value[1]);
                return;
            }

            Long[] next_value;

            long res;
            if((res = mul(value[0])) <= B && !visited.getOrDefault(res, false)) {
                next_value = new Long[]{res, value[1] + 1};
                deque.add(next_value);
                visited.put(res, true);
            }

            if((res = add_right(value[0])) <= B && !visited.getOrDefault(res, false)) {
                next_value = new Long[]{res, value[1] + 1};
                deque.add(next_value);
                visited.put(res, true);
            }
        }

        System.out.println(-1);
    }
}