백준 16953번: A -> B C++ 코드(BFS)

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

int bfs(long long a, long long b){
    queue <pair <long long, long long> > q;
    q.push(make_pair(a, 1));
    while(!q.empty()){
        pair <long long,long long> now = q.front();
        q.pop();
        if(now.first == b){
            return now.second;
        }
        if(now.first*2 <= b){
            q.push(make_pair(now.first*2, now.second+1));
        }
        if(now.first*10+1 <= b){
            q.push(make_pair((now.first*10)+1, now.second+1));
        }
    }
    return -1;
}

int main(){
    long long a,b;

    cin >> a >> b;
    cout << bfs(a,b);
}

 

설명

숨바꼭질 문제와 비슷한 느낌이다. bfs함수를 만들 때, 무한루프가 발생하지 않도록, 연산한 수가 B를 넘는다면 큐에 안넣는 조건문을 달아주어야한다. 그리고 필자는 카운트를 큐에 담을때 증가하는 식으로 해서 카운트의 시작값을 1로 설정하였다.