[C++] A → B (백준 16953번)

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

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int INTMAX = 1000000000;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long a, b;
    cin >> a >> b;

    queue<pair<long long, int>> q;
    q.emplace(a, 0);
    int ans = -1;

    while (!q.empty()) {
        long long x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (x == b) {
            ans = cnt;
            break;
        } else if (x < b) {
            q.emplace(x * 2, cnt + 1);
            q.emplace(10 * x + 1, cnt + 1);
        }
    }

    if (ans == -1) cout << -1 << '\n';
    else cout << ans + 1 << '\n';
}

전형적인 bfs 문제였다. 큐에 <현재의 수, 현재까지 사용한 연산의 수>를 pair로 넣고 반복하였다. 2를 곱하는 연산과 1을 수의 가장 오른쪽에 추가하는 연산 모두 값이 무조건 커지는 연산이기 때문에 따로 vst 배열은 만들지 않고 대신 목표 값보다 커지면 큐에 집어넣지 않도록 하였다.

주의할 점은 x와 b 모두 long long으로 선언해주어야 한다는 점이다. x는 10^9에 2를 곱한 결과가 들어갈 수 있기 때문에 long long이어야 하고, b는 long long과 비교해야 하기 때문에 long long이어야 한다. (AC)