[백준] 16953번 : A → B – JAVA [자바]

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

 

 

---

문제

 

 

---

해결 방법

이 문제는 BFS(너비 우선 탐색) 를 활용하여 해결할 수 있다. BFS는 최단 경로를 찾는 데 유용한 알고리즘이기 때문에, 최소 연산 횟수를 구하는 데 적합하기 때문이다. 만약에 다른 방법을 이용해서 이 문제를 풀었다면 댓글로 공유해주기 바란다.

 

1. 큐 (Queue)를 활용하여 탐색을 진행한다.

2. 시작 값 A를 큐에 넣고, 연산을 수행하며 다음 숫자들을 큐에 추가한다. 다음 숫자들은 2를 곱한 숫자나 뒷자리에 1을 추가한 숫자를 뜻한다.

3. 새로운 숫자가 B보다 작다면 계속 진행하고, B와 같다면 연산 횟수를 출력하고 종료한다. 새로운 숫자가 B보다 크면 B가 절대로 될 수 없다 (새로운 숫자는 2를 곱한 값이나 뒷자리에 1을 추가한 값이므로 무조건 B보다 크기 때문에).

4. 큐가 비었는데도 B를 만들 수 없다면 -1을 출력한다.

 

---

코드 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        
        System.out.println(bfs(a, b));
    }
    
    public static int bfs(long a, long b) {
        Queue<Long> queue = new LinkedList<>();
        Map<Long, Integer> visited = new HashMap<>();
        
        queue.add(a);
        visited.put(a, 1);
        
        while (!queue.isEmpty()) {
            long current = queue.poll();
            int count = visited.get(current);
            
            long next1 = current * 2;
            long next2 = current * 10 + 1;
            
            if (next1 == b || next2 == b) {
                return count + 1;
            }
            
            if (next1 < b && !visited.containsKey(next1)) {
                queue.add(next1);
                visited.put(next1, count + 1);
            }
            
            if (next2 < b && !visited.containsKey(next2)) {
                queue.add(next2);
                visited.put(next2, count + 1);
            }
        }
        return -1;
    }
}

 

 

---

코드 설명

 

1. bfs 함수에서 Queue 와 Map 을 활용해 탐색을 진행한다. 여기서 이 맵이 방문 여부를 체크한다.

2. queue 에 현재 숫자를 넣고, visited 맵을 사용하여 방문 여부를 체크한다.

3. 현재 숫자에서 두 가지 연산을 수행한 결과(next1, next2)를 확인한다.

4. 만약 b 를 만들 수 있다면 현재 횟수 +1을 출력하고 종료한다.

5. 아직 b 를 만들지 못했다면, b 보다 작은 숫자들만 queue 에 추가하여 탐색을 이어간다.

6. BFS가 끝날 때까지 b 를 찾지 못하면 -1 을 반환한다.

 

---

시간 복잡도 분석

 

이 문제에서 각 숫자에 대해 두 가지 연산(곱하기 2, 끝에 1 추가)을 수행하므로, 한 단계마다 경우의 수가 두 배로 증가한다. 따라서 연산이 진행될 때마다 탐색해야 할 숫자가 기하급수적으로 증가할 수 있다.

최대 숫자 B까지 탐색하는 과정에서, 각 단계마다 숫자가 적어도 두 배씩 증가하므로 전체 연산 횟수는 대략 O(log B) 가 된다. 이는 이진 트리에서의 BFS 탐색과 유사한 개념이다.

B의 최대 크기가 10억(10^9)이므로, BFS 탐색으로도 충분히 해결할 수 있다. 최악의 경우에도 탐색 깊이는 약 30~40 수준이므로, 시간 내에 충분히 계산이 가능하다.