코영방

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

#include <bits/stdc++.h>
using namespace std;
//숨바꼭질 4
int main(void) {
    queue<int> q;
    int n, m, visited[10000] = {0,}, time[10000] = {0,};
    cin >> n >> m;

    q.push(n);
    visited[n] = 1;

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now == m) {
            printf("%d\n", time[m]);
            break;
        }
        if (time[now-1] >= 0 && visited[now-1] == 0) {
            q.push(now-1);
           visited[now-1] = 1;
           time[now-1] = time[now] + 1;
        }
        if (time[now+1] <= 10000 && visited[now+1] == 0) {
            q.push(now+1);
            visited[now+1] = 1;
            time[now+1] = time[now] + 1;
        }
        if (time[now*2] <= 10000 && visited[now*2] == 0) {
            q.push(now*2);
            visited[now*2] = 1;
            time[now*2] = time[now] + 1;
        }
    }
    int path[10000], index = 0;
    int now = m;
    path[index] = now;
    index++;
    while(now != n) {
        //printf("===%d \n", now);
        if (now-1 >= 0 && visited[now-1] == 1 && time[now-1] == time[now]-1) {
            now = now - 1;
        }
        else if (now+1 <= 10000 && visited[now+1] == 1 && time[now+1] == time[now]-1) {
            now = now+1;
        }
        else if (now % 2 == 0 && visited[now/2] == 1 && time[now/2] == time[now]-1) {
            now = now/2;
        }
        path[index] = now;
        index++;
    }
    //return 0;

    for (int i=index-1; i>=0; i--) {
        printf("%d ", path[i]);
    }

    return 0;
}