[백준 / Java] 16953: A → B (BFS)

난이도: Silver 2

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

 

문제

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

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

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

입력

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

출력

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

---

 

이 문제는 그리디 알고리즘으로 분류가 되어있으나, 나는 BFS로 풀었다.

흔한 BFS 문제들과 다른 점은 주어진 수의 최대 범위가 10억으로 너무 커서 이 값으로 배열 인덱스를 초기화할 경우 메모리 초과 예외가 발생한다.

그러므로 graph와 visited를 배열로 만들기보다는, graph는 사용하지 않고 visited를 Set으로 만들어야 한다.

graph를 만들지 않는 대신, 큐의 크기만큼 반복해서 다음 값들을 큐에 삽입하고 visited(set)에 삽입하면 된다.

큐의 크기만큼 다 반복했으면, 그때 depth(깊이)를 1 증가시키면 된다.

 

일단 이 문제를 풀기 위해 논리적인 트리 그림을 그려 보자.

문제에 주어진 예시는 A = 2, B = 162이다.

A * 2와 A * 10 + 1의 과정을 반복하면서 B를 찾을 때까지 자식 노드를 추가하자.

 

 

B = 162를 찾을 때까지의 트리는 이러하다.

맨 위 2에서 162까지는 5번을 거치면 된다.

맨 처음 노드의 깊이를 1로 설정하면, 목적지 노드까지의 깊이는 5가 된다.

 

 

주석에 설명을 한 줄 한 줄 자세히 적어 놓았다.

자세한 방법은 코드를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class P16953_A에서B {
    static int A, B;
    
    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());    // 도착 숫자
        System.out.println(bfs());    // bfs를 수행하면서 도착 숫자까지의 트리 깊이 출력
    }
    
    public static int bfs() {
        Queue<Long> queue = new LinkedList<>();        // bfs 수행을 위한 큐
        // 주어진 수의 최대 범위가 10억이므로, 방문 체크할 visited는 배열로 만들지 않고 Set으로 만듦
        Set<Long> visited = new HashSet<>();        
        int depth = 1;    // 트리의 깊이
        
        queue.add((long)A);        // 큐에 출발 숫자 삽입
        visited.add((long)A);    // 방문 체크할 set에 출발 숫자 삽입
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int size = queue.size();    // 큐의 현재 크기 구하기
            
            // 큐의 크기만큼 반복
            for (int i = 0; i < size; i++) {
                long now = queue.poll();    // 큐에서 현재 숫자 뽑기
                
                if (now == B) {        // 현재 숫자가 도착 숫자와 같다면
                    return depth;    // 현재 트리의 깊이 리턴
                }
                
                long next1 = now * 2;    // 자식 노드로 추가할 숫자는 현재 숫자 * 2
                // 자식 노드로 추가할 숫자가 도착 숫자 이하이거나, 방문 체크 set에 없는 값이라면
                if (next1 <= B && !visited.contains(next1)) {
                    queue.add(next1);    // 큐에 다음 숫자 삽입
                    visited.add(next1);    // 방문 체크할 set에 다음 숫자 삽입
                }
                
                long next2 = now * 10 + 1;    // 자식 노드로 추가할 숫자는 현재 숫자 맨 뒤에 1 추가
                // 자식 노드로 추가할 숫자가 도착 숫자 이하이거나, 방문 체크 set에 없는 값이라면
                if (next2 <= B && !visited.contains(next2)) {
                    queue.add(next2);    // 큐에 다음 숫자 삽입
                    visited.add(next2);    // 방문 체크할 set에 다음 숫자 삽입
                }
            }
            
            depth++;    // 큐의 크기를 구할 시점에 큐에 들어있었던 숫자들을 모두 뽑았다면 트리의 깊이 1 증가
        }
        
        return -1;        // 도착 숫자(찾아야 할 숫자)가 없다면 -1 리턴
    }
}