13913 숨바꼭질 4

문제 링크

• 내 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, K;
int n[100001];

int solve()
{
    for (int i = 0; i < 100001; i++)
        n[i] = -1;

    queue<int> q;
    q.push(N);

    n[N] = N;

    int t = 0;

    while (!q.empty())
    {
        int sz = q.size();
        while (sz--)
        {
            int fr = q.front();
            q.pop();

            if (fr == K)
                return t;

            if (fr - 1 >= 0 && n[fr - 1] == -1)
            {
                n[fr - 1] = fr;
                q.push(fr - 1);
            }
            if (fr + 1 < 100001 && n[fr + 1] == -1)
            {
                n[fr + 1] = fr;
                q.push(fr + 1);
            }
            if (fr * 2 < 100001 && n[fr * 2] == -1)
            {
                n[fr * 2] = fr;
                q.push(fr * 2);
            }
        }
        t++;
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    int ans = solve();

    cout << ans << "\n";

    vector<int> stk;
    stk.push_back(K);
    while (n[K] != K)
    {
        stk.push_back(n[K]);
        K = n[K];
    }
    for(auto s = stk.rbegin(); s != stk.rend(); s++)
        cout << *s << " ";
    cout << "\n";

    return 0;
}