[BOJ/16953번A->B] c++ / BFS

문제

A를 B로 바꾸기 위해 필요한 연산의 최소 개수를 구하는 문제

-2를 곱하거나 숫자 뒤에 1을 붙이는 연산 두가지가 존재

 

생각

큐에 연산 두가지를 각각 넣어주면 되겠다고 생각함

 

문제풀이

1.정수 A, B를 입력받음

2.BFS 탐색함

-만약 연산된 A가 B와 같아지면 함수 종료

-만약 A*2가 B보다 작다면 큐에 A*2, cnt+1 푸쉬

-만약 A*10+1이 B보다 작다면 큐에 A*10+1, cnt+1 푸쉬

3.함수에서 반환된 수 출력

 

처음에 문제를 똑바로 안보고 int 형으로 풀었음 .. 문제 잘 읽기!!!

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define X first
#define Y second
long long A, B;
long long BFS() {
    queue<pair<long long, long long>> Q;
    Q.push({A, 1}); // A와 cnt = 1
    while (!Q.empty()) {
        pair<long long, long long> cur = Q.front(); Q.pop();

        if ( cur.X == B ) 
            return cur.Y;
        if (cur.X * 2 <= B )
            Q.push({cur.X*2, cur.Y+1});
        if ( cur.X*10 + 1 <= B )
            Q.push({cur.X*10+1, cur.Y+1});
    }

    return -1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> A >> B;
    cout << BFS();
}