백준 16953. A->B

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

16953번: A → B

 

2차원 벡터에 트리를 만드는 형태로 풀었다.

트리의 행번호가 그 숫자를 만드는데 연산을 수행한 횟수라고 할수 있다.

행에 모든 원소들에 대하여 2를곱한값, 1을추가한 값을 다음 행에 푸쉬하는 형태로 트리를 만들고

B를 찾으면 반복문을 탈출하도록 했다.

 

#include <iostream>
#include <vector>
using namespace std;
#define MAX 1000000000 // 10^9

vector<long long> v[10000000];

int main()
{
    long long A, B;
    cin >> A >> B;

    if(A == B)
    {
        cout << 1;
        return 0;
    }

    v[0].push_back(A);

    int row = 0;
    bool flag = false;
    bool fail = false;
    while(true)
    {
        // 트리의 가장 왼쪽 자식이 가장 작은값
        // 가장 작은값이 B를 넘어버리면 반복문 종료
        if(v[row][0] > B) break;

        for(int i = 0; i < v[row].size(); i++)
        {
            long long times = v[row][i] * 2;
            long long addOne = (v[row][i] * 10) + 1;

            if(times == B || addOne == B)
            {
                flag = true;
                break;
            }
            if(times <= B)
                v[row+1].push_back(times);
            if(addOne <= B)
                v[row+1].push_back(addOne);

            // 트리의 다음 행에 아무것도 푸쉬하지 않았다면 B로 바꿀수없다, 탈출
            if(v[row+1].empty())
            {
                fail = true;
                break;
            }

        }

        if(flag || fail) break;
        row++;
    }

    // B를 찾음
    if(flag)
        cout << row+2;
    else
        cout << -1;
}

 

---

이후에 다른 분들이 푼것을보고 bfs로 풀어봤다

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

long long A,B;

int main()
{
    cin >> A >> B;

    // num, row
    queue<pair<long long, long long>> q;
    q.push({A,1});

    bool flag = false;
    int ans;

    // bfs
    while(!q.empty())
    {
        long long num = q.front().first;
        long long row = q.front().second;
        q.pop();

        long long times = num*2;
        long long addOne = (num*10)+1;

        if(times == B || addOne == B)
        {
            flag = true;
            ans = row+1;
            break;
        }

        if(times <= B)
            q.push({times, row+1});
        if(addOne <= B)
            q.push({addOne, row+1});
    }

    if(flag)
        cout << ans;
    else
        cout << -1;

}