BOJ 13913 숨바꼭질 4

1 개요[ | ]

BOJ 13913 숨바꼭질 4
2 같이 보기[ | ]

3 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

int N, K;
int dist[1000001];
int from[1000001];
int INF=INT_MAX/2;

void solve() {
    fill(dist, dist+1000001, INF);
    queue<int> q;
    q.push(N);
    dist[N] = 0;
    int x, nx, answer;
    while(!q.empty()) {
        x = q.front();
        q.pop();
        if(x == K) return;
        for(int i=0; i<3; i++) {
            if(i==0) {
                nx = x*2;
            } else if(i==1) {
                nx = x+1;
            } else {
                nx = x-1;
            }
            if(nx<0 || nx>1000000 || dist[nx]<dist[x]+1) continue;
            dist[nx] = dist[x]+1;
            from[nx] = x;
            q.push(nx);
        }
    }
}

int main() {
    cin >> N >> K;
    solve();
    cout << dist[K] << '\n';
    deque<int> dq = {K};
    while(dq.front() != N) {
        dq.push_front(from[dq.front()]);
    }
    for(int el: dq) {
        cout << el << ' ';
    }
}