[BOJ] 16953

A → B

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

분류

• Silver 1

• 그래프 이론
• 그리디 알고리즘
• 그래프 탐색
• 너비 우선 탐색

해법

BFS를 이용하는 문제입니다.

각 값에 대해 2를 곱하는 연산과 끝에 1을 붙이는 연산을 수행한 값을 큐잉해주면서 확인해주면 됩니다.

정답 코드

/*
BOJ 16953: A -> B
*/

#include <bits/stdc++.h>
using namespace std;

int a, b;
int ans = 0;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> a >> b;
    queue<int> q;
    q.push(a);
    while (!q.empty()) {
        ans++;
        int sz = q.size();
        while (sz--) {
            int cur = q.front(); q.pop();
            int next1 = cur * 2, next2 = cur * 10 + 1;
            if (next1 == b || next2 == b) {
                cout << ans + 1;
                return 0;         
            }

            if (0 < next1 && next1 <= b / 2) q.push(next1);
            if (0 < next2 && next2 <= b / 2) q.push(next2);
        }
    }
    cout << -1;
    return 0;
}