(C++) - 백준(BOJ) 16953번 : A → B

www.acmicpc.net/problem/16953

16953번: A → B

bfs 문제였습니다.

 

 

풀이방법

 1. 원하는 수 b에 도착했을 때 지나온 길을 세주기 위해 queue를 pair로 선언합니다. 이 때 int 범위를 *10 + 1 연산을 하거나 *2를 했을 때 초과할 수 있으므로 long long자료형으로 선언하도록 합니다.

 2. bfs를 실행합니다. 매번 pop을 하여 횟수와 값을 봅니다. x*2 <= b일 때, x*10+1 <= b일 때 해당 노드를 push해줍니다. x == b인 경우가 여러가지 방법이 있을 수 있으니 해당 횟수가 가장 적은 값을 ans에 저장합니다.

 3. 정답을 반환합니다. 정답을 못찾아 초기값일 때는 -1을 반환합니다.

 4. 정답을 출력합니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
using pll = pair <ll,ll>;
ll a,b;

int bfs(){
    ll ans = 0x7f7f7f7f;
    queue <pll> q;
    q.push({a,1});
    while(!q.empty()){
        ll x = q.front().first;
        ll cnt = q.front().second;
        ll plusOne = x * 10 + 1;
        q.pop();
        if(x == b) ans = min (ans,cnt);
        if(x * 2 <= b ) q.push({x * 2, cnt + 1});
        if(plusOne <= b ) q.push({plusOne, cnt + 1});
        cnt++;
    }
    if(ans == 0x7f7f7f7f) return -1;
    return ans;
}

int main(){
    cin >> a >> b;
    cout << bfs();
}