백준 13913 숨바꼭질 4

앞선 숨바꼭질 문제와 같다.

추가된 것이 있다면 답을 찾아가는 경로를 출력해야 한다.

그래서 경로를 저장하기 위한 배열 d를 하나 더 둔다.

 

도착지에서부터 출발지로 가면서 stack에 쌓은 후 pop하면서 출력한다.

물론 재귀 함수 호출을 통해서 출력해도 된다.

코드는 아래와 같다.

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
 
int time[100001];
int d[100001];
 
int main(int argc, char** argv) {
    int n, k;
    cin >> n >> k;
 
    for (int i = 0; i < 100001; i++)time[i] = -1;
 
    queue<int> q;
    q.push(n);
    time[n] = 0;
 
    while (!q.empty()) {
        int position = q.front();
        q.pop();
 
        int prev = position - 1;
        int next = position + 1;
        int jump = position * 2;
 
        if (prev >= 0) {
            if (time[prev] == -1) {
                time[prev] = time[position] + 1;
                d[prev] = position;
                q.push(prev);
            }
        }
        if (next < 100001) {
            if (time[next] == -1) {
                time[next] = time[position] + 1;
                d[next] = position;
                q.push(next);
            }
        }
        if (jump< 100001) {
            if (time[jump] == -1) {
                time[jump] = time[position] + 1;
                d[jump] = position;
                q.push(jump);
            }
        }
    }
 
    printf("%d\n", time[k]);
    stack<int> s;
    s.push(k);
    while (k != n) {
        s.push(d[k]);
        k = d[k];
    }
    while (!s.empty()) {
        int x = s.top();
        s.pop();
        printf("%d ", x);
    }
 
    return 0;
}