[백준] 16953번 - A → B (Silver 2)

문제 링크

백준 16953번 - A $\rightarrow$ B (Silver 2)

문제 설명

정수 A를 2를 곱하거나, 1을 오른쪽에 추가하는 두 가지 연산만을 이용하여 B로 바꾸려고 한다.
A를 B로 바꿀 때 필요한 연산의 최소 개수를 구하면 된다.

정답 코드 및 설명

노드 A에서 노드 2A, 노드 10A+1가 연결되어 있는 그래프라고 생각할 수 있다.
노드 A에서 출발하여 노드 B에 도착하는 최소 거리를 구하는 문제이므로 BFS가 유용하다.

BFS(Breadth-First Search, 너비 우선 탐색)은 DFS와 대응되는 그래프의 탐색 방식이다.
시작 노드의 모든 자식들을 탐색하고, 그 다음에는 자식의 자식들을 탐색하고 하는 과정의 반복이다.
거리가 짧은 순으로 탐색하므로, 최소 거리를 구하는데 유용한 알고리즘이다. 보통 큐를 활용하여 구현한다. 과정을 요약하면 아래와 같다.

1. 시작 노드를 큐에 넣는다.
2. 큐의 맨 앞의 원소를 빼내고, 빼낸 원소의 자식 노드들을 큐에 넣는다.
3. 2를 큐가 빌 때까지 반복한다.

BFS 역시 경우에 따라서 이미 노드를 방문했는지 체크해주어야 한다.
그래프에 사이클이 있는 경우 무한 루프에 빠질 수도 있기 때문이다. 이 문제에는 해당하지 않는다.

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

public class Main {

    static int a, b;
    static Queue<long[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        bw.write(bfs() + "");
        bw.close();
    }

    static long bfs() {
        long start[] = { a, 1 };
        queue.add(start);
        while (!queue.isEmpty()) {
            long num[] = queue.poll();
            if (num[0] == b)
                return num[1];
            if (num[0] * 2 <= b) {
                long newNum[] = { num[0] * 2, num[1] + 1 };
                queue.add(newNum);
            }
            if (num[0] * 10 + 1 <= b) {
                long newNum[] = { num[0] * 10 + 1, num[1] + 1 };
                queue.add(newNum);
            }
        }
        return -1;
    }
}