BOJ 13913 숨바꼭질 4

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

이번 문제는 경로를 추적해서 출력하는 문제였다.

조금만 생각해보면 금방 알 수 있는데, 현재 위치를 지나가는 배열 a를 만들어서

a[next] = cur 를 담고있다고 가정해보면 a[k] 에는 k에 도착하기 전 가장 마지막 위치가 담겨있을 것이고,

a[마지막 위치] 에는 그 위치에 오기 위한 위치가 점진적으로 들어있을 것이다.

 

그렇다면 구현은 간단하다.

기존 bfs를 통해 최단시간을 구할 때 a[next] = cur 만 추가해주고 이후에 재귀적인 호출을 통해

역추적해주면 된다.

 

 

#include <iostream>
#include <queue>
using namespace std;
 
int a[100001], n, k;
int vis[100001];
queue<int> q;
 
void backtrace(int cur) {
    if (cur == n) {
        cout << n << ' '; return;
    }
    backtrace(a[cur]);
    cout << cur << ' ';
}
 
int main() {
    cin >> n >> k;
 
    q.push(n);
 
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == k) break;
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) {
                vis[i] = vis[cur] + 1;
                q.push(i);
                a[i] = cur;
            }
        }
    }
 
    cout << vis[k] << endl;
    backtrace(k);
    cout << endl;
 
    return 0;
}