[백준 16953번] [BFS] A → B

앞의 술레잡기 문제와 비슷하게

가중치가 동일한 문제의 최단거리는 BFS로 처리할 수 있다.

(만약 그렇지 않은 경우는 Dijikstra로 처리해야 한다.)

 

이 문제의 경우는 숫자가 겹칠 일이 없으므로 딱히 visited를 처리해서 진행해주지 않아도 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int main(void){
    fastio;
    queue<pll> data_store;
    int a, b;
    cin >> a >> b;
    data_store.push(make_pair(a, 0));

    while(data_store.size() != 0){
        pll check_value = data_store.front();
        data_store.pop();

        if(check_value.first == b){
            cout << check_value.second + 1 << "\n";
            return 0;
        }
        else if(check_value.first > b) continue;

        data_store.push(make_pair(check_value.first * 2, check_value.second + 1));
        data_store.push(make_pair(check_value.first * 10 + 1, check_value.second + 1));
    }

    cout << "-1\n";

    return 0;
}