[BFS] 숨바꼭질 4

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
 
int n, k;
int visit[100001]= {  0 };
int route[100001]={ -1, };
vector<int> path; //경로 저장
 
int bfs(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == k) {
            int idx = x;
            while (idx != n) {
                path.push_back(idx);
                idx = route[idx];
            }
            path.push_back(n);
            return visit[x] - 1;
        }
        if (x + 1 <= 100000 && visit[x + 1] == false) {
            visit[x + 1] = visit[x] + 1;
            route[x + 1] = x;
            q.push(x + 1);
        }
        if (x-1 >= 0 && x - 1 <= 100000 && visit[x - 1] == false) {
            visit[x - 1] = visit[x] + 1;
            route[x - 1] = x;
            q.push(x - 1);
        }
        if (x * 2 <= 100000 && visit[x * 2] == false) {
            visit[x *2] = visit[x] + 1;
            route[x *2] = x;
            q.push(x *2);
        }
    }
}
 
int main() {
    cin >> n >> k;
    cout << bfs(n)<<endl;
    for (int i = 0; i <= 2 * k; i++) {
        cout << route[i]<<" ";
    }
    cout << endl;
 
    //거꾸로 저장되어있으므로
 
    for (int i = path.size() - 1; i >= 0; i--)
 
        cout << path[i] << " ";
 
    cout << endl;
    return 0;
}