백준 13913번: 숨바꼭질 4 (C++)

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

숨바꼭질 시리즈의 네 번째 문제이다. 이 문제는 최단 시간을 구해주고, 동시에 경로를 같이 출력해주면 된다.

경로를 출력하는 방법에는 여러가지가 있을 수 있겠지만, 현재 노드를 다음 노드의 부모라고 보고 parent 배열에 저장해주었다.

다만 이렇게 할 경우, 시작점과 목적지가 같은 경우에 올바른 경로를 출력할 수 없기 때문에 따로 예외 처리를 해주어야 한다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int src, dst, m[100002], dr[3] = { 0,1,2 }, dis[100002]; //-1, +1, *2
bool vis[100002];
vector<int> path;
queue<int> q;
int parent[100002];
void bfs() {
    
    q.push(src);
    dis[src]++;
    
    path.push_back(src);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < 3; i++) {
            int np;
            if (dr[i] == 0) np = cur - 1;
            else if (dr[i] == 1) np = cur + 1;
            else
                np = cur * 2;
 
            if (np < 0 || np > 100000 || dis[np] >= 0) continue;
            
            path.push_back(np);
            
            parent[np] = cur; //현재 노드를 다음 노드의 부모로 저장
            q.push(np);
            dis[np] = dis[cur] + 1;
 
        }
    }
}
 
int main(void) {
 
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    cout << dis[dst] << '\n';
    if (src == dst) cout << src; //출발지와 목적지가 같은 경우 예외 처리
    else {
        int prev = parent[dst];
        vector<int> v;
        v.push_back(dst);
        v.push_back(prev);
        while (1) {
            if (prev == src) break; //출발지가 나올 때까지 타고 올라감
            prev = parent[prev];
            v.push_back(prev);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i] << ' ';
    }
 
    return 0;
}