[백준 A->B (A to B)] C++ (풀이, 코드, BFS)

문제 링크

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

16953번: A → B

 

문제

 

 

풀이 및 코드

 

아주 간단한 그래프 문제중에 가장 예시라고 생각합니다.

 

문제의 조건에서 

1) 2를 곱한다.

2) 10을 곱하고 1을 더한다. 

를 통해 너비탐색을 하게 되면서 만약 주어진 B의 숫자와 같아지게 된다면 return을 하는 문제라고 생각합니다.

 

여기서 추가적으로 

끝자리가 3,5,7,9는 절대적으로 불가능하니 처음에 2로 나눠지지 않거나 끝자리가 1이 아니라면 -1을 리턴하였습니다!

짝수이거나 무조건 홀수는 1이 아니면 -1 return 즉 -> 3,5,7,9는 애초에 안됨

 

#include <iostream>

#include <queue>

using namespace std;

int main(){

    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    long a,b;

    cin>>a>>b;

    //3,5,7,9에 대한 처리

    if(b % 10 != 1 && b % 2 !=0){

        cout<<"-1";

        return 0;

    }

    queue<pair<long,int>> q;

    q.push(make_pair(a,1));

    while(!q.empty()){

        long num = q.front().first;

        int cnt = q.front().second;

        q.pop();

        long twoMulti = num * 2;

        long plusOne = num*10 + 1;

        if(twoMulti == b || plusOne == b){

            cout<<cnt+1;

            return 0;

        }

        if(twoMulti < b)

            q.push(make_pair(twoMulti,cnt+1));

        if(plusOne < b)

            q.push(make_pair(plusOne,cnt+1));

    }

    cout<<"-1";

}