[Algorithm/Java] 백준 16953번 - A → B

---

https://www.acmicpc.net/problem/16953

---

📌 문제

문제 유형

• 그래프

📘 문제 설명

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

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

📥 입력

2 162

📥 출력

5

🔍 문제 풀이

어떤 알고리즘을 써야할까?

DFS는 최단경로를 보장하지 않고, DP는 상태 수(최대 10억)가 너무 많아 비효율적이다.

따라서 최단 연산 횟수를 탐색하기 위해 BFS(너비 우선 탐색)를 사용해야 한다.

문제 해결 절차

1. 입력값 a, b를 long으로 받는다
2. 가능한 연산을 큐에 적용한다
   • 현재 수 cur에서 다음 수로 이동할 수 있는 연산은 두 가지이다.
     • 현재 수에 2를 곱하기: cur *2
     • 현재 수의 가장 오른쪽에 1을 추가하기: cur * 10 + 1
3. BFS로 최소 연산 횟수를 단계별로 탐색한다
4. 현재 값이 b보다 크면 연산하지 않는다.

⚠️ 숫자가 매우 커질 수 있기 때문에 Deque<Long>을 사용하자.

• int는 최대 약 2.1 * 10^9 까지 표현 가능하다.
• 문제의 입력값 a, b는 int로 커버 가능하지만, 연산 cur * 10 + 1을 하면 최대 10^10 이상까지 커질 수 있다.
• 따라서 이 문제에서는 오버플로우 방지를 위해 long 을 사용해야한다!

연산 횟수를 추적하는 방법

dq.size() 기반 레벨 방식 (레벨별로 cnt++)

• 한 레벨에서 큐에 있던 노드 수(dq.size())만큼만 처리 후 cnt++ 하는 방식이다.
• 각 숫자마다 몇 번의 연산을 거쳐 도달했는지를 함께 저장한다.

📌 놓친 점

dq.size()를 사용해 현재 큐의 크기를 미리 저장해놔야 한다.

• dq.size()는 BFS에서 현재 단계(레벨)의 연산 횟수를 정확히 계산하기 위해 필요하다.
• 저장해두지 않고 그냥 b보다 작을때까지 반복을 돌면, b보다 작기만 하면 계속 큐에 넣게 된다.
• 그 결과 레벨(=연산 횟수 단계)이 섞여버려서 cnt를 정확히 셀 수 없게 된다.
• 그래서 size을 먼저 저장해두고, 그 개수만큼만 반복해야 이번 레벨에서 도달한 노드들(수)들만 처리하고 cnt++를 통해 연산 횟수를 1 증가시킬 수 있다.

int level = dq.size(); // 현재 큐 크기 미리 저장해놓기

visited[]가 없어도 된다.

연산이 두 가지 밖에 없으며, 모든 연산이 항상 값이 커지기만 한다.

즉, 같은 숫자를 중복으로 다시 방문할 일이 거의 없다 -> 무한루프 걱정 X

💻 전체 코드

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

public class Main {
    static int a, b;
    static int cnt = 1;

    public static void bfs(){
        Deque<Long> dq = new ArrayDeque<>();
        dq.offer((long) a);

        while(!dq.isEmpty()){
            int level = dq.size(); //현재 레벨에 있는 노드 수 (같은 연산 횟수 단계)

            for(int i=0; i<level; i++){
                long cur = dq.poll();

                if(cur == b){
                    System.out.println(cnt);
                    return;
                }
                if (cur * 2 <= b) dq.offer(cur * 2);
                if (cur * 10 + 1 <= b) dq.offer(cur * 10 + 1);
            }
            cnt++; // cnt는 레벨마다 1씩 증가함
        }
        System.out.println(-1);
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        bfs();
    }
}