[C++] 백준 16935번 - A -> B (BFS)

문제 링크 : https://www.acmicpc.net/problem/16953

16953번: A → B

 

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

 

---

 

접근 방법

- BFS를 이용한 완전탐색 문제이며, 자료형에 주의해야하는 문제이다.

- 주어진 입력 값 범위가 1부터 10^9 (십억)인데, 두번째 연산을 할 때 int형 범위가 넘어가므로 a, b 모두 long 형으로 선언해줘야함에 주의하자! 

- 두개의 연산 모두 원래의 값보다 증가하는 연산이므로, 연산 후 결과 값이 b를 넘어가면 que에 담지 않는다. 

 

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main()
{

    long a, b;
    cin >> a >> b;

    queue<pair<long, long>> que;
    que.push(make_pair(a, 0));
    long answer = 0;

    bool flag = false;
    while (!que.empty())
    {

        long num = que.front().first;
        long cnt = que.front().second;
        que.pop();

        if (num == b)
        {
            answer = cnt;
            flag = true;
            break;
        }
        
        if(num*2 <= b){
            que.push(make_pair(num * 2, cnt + 1));
        }
        if (num * 10 + 1 <= b){
            que.push(make_pair(num * 10 + 1, cnt + 1));
        }

            
    }

    if (flag)
        cout << answer + 1;
    else
        cout << -1;
}