[백준 16953번] A -> B

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

16953번: A → B

<문제 풀이>  BFS 알고리즘

 

큐에 다음 두 가지를 삽입하는 BFS를 구현하면 되는 문제입니다.

1. cur * 2 

2. cur * 10 + 1 

 

큐가 비워지기 전에 A == B가 되는 수를 찾으면 성공이고 큐가 비워졌을 때 A == B가 되는 수를 못 찾으면 실패입니다.

 

숫자 맨 뒤에 1을 추가하는 것은 2로 나누어 떨어지지 않기 때문에 숫자에 2를 곱한 것과 중복되지 않습니다.

따라서 방문 체크 배열을 만들 필요가 없습니다.

 

숫자는 최대 10^9이므로 2번 연산에서 10^9 * 10 + 1을 하면 int의 최대 크기를 넘어가기 때문에 long long 자료형을 사용해야 합니다.

 

 

<C++소스코드>

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
#include<utility>
using namespace std;
 
#define X first
#define Y second
typedef long long ll;
 
ll A, B;
void bfs() {
    queue<pair<ll, ll> >Q;
    Q.push({A * 2, 1}); //2를 곱한다.
    Q.push({A * 10 + 1, 1}); // 1을 수의 가장 오른쪽에 추가한다.
    long long cnt = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur.X == B) {
            cout << cur.Y + 1;
            return;
        }
        if (cur.X * 2 <= B) {
            Q.push({ cur.X * 2, cur.Y + 1 }); //2를 곱한다.
        }
        if (cur.X * 10 + 1 <= B) {
            Q.push({ cur.X * 10 + 1 , cur.Y + 1}); // 1을 수의 가장 오른쪽에 추가한다.
        }
    }
    cout << "-1";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> A >> B;
 
    bfs();
    
 
    return 0;
}