[BOJ-13913]숨바꼭질4

앞선 숨바꼭질1과 동일한 출력을 하는데 

이때 그 경로를 출력하는 것이 추가된 문제이다.

음......

X1 = here-1

X2 = here+1

X3 = 2*here 이라고 하면,

0. BFS탐색을 하고,

1. Q에 집어넣는 인자(X1, X2, X3)의 here를 되돌아 갈수 있는 위치로 삼는다. (이것은 here에서 이곳(X1, X2, X3)으로 이동하였다는 의미가 된다. 

2. 그렇다면 X1/X2/X3 로 이동을 하면서 도착지 까지 반복한다.

그리고 최단경로를 출력하고,

저장된 경로를 역으로 추적하여 vector<int> 에 넣고, 역으로 벡터배열을 출력한다.

음.. 네트워크 플로우 문제 풀어본기억이나서 parent를 지정하는 게 생각나서 바로 풀 수 있었던 것 같다.

#include<cstdio>
#include<queue>
#include<memory.h>
#include<vector>
using namespace std;
 
const int MAX = 100001;
int sta, fin;
int vis[MAX];
int parent[MAX];
int main(){
    scanf("%d%d", &sta, &fin);
    memset(vis, -1, sizeof(vis));
    memset(parent, -1, sizeof(parent));
    queue<int> q;
    q.push(sta);
    vis[sta] = 0;
 
    while(!q.empty()){
        int here = q.front(); q.pop();
 
        if(here == fin) break;
 
        if(here-1 >= 0)
            if(vis[here-1]==-1) vis[here-1] = vis[here]+1, parent[here-1] = here, q.push(here-1);
        if(here+1 < MAX)
            if(vis[here+1]==-1) vis[here+1] = vis[here]+1, parent[here+1] = here, q.push(here+1);
        if(2*here < MAX)
            if(vis[2*here]==-1) vis[2*here] = vis[here]+1, parent[2*here] = here, q.push(2*here);
    }
 
    printf("%d\n",vis[fin]);
 
    vector<int> v;
    for(int par = fin ; par != -1 ; par = parent[par]) v.push_back(par);
    for(auto iter = v.rbegin() ; iter != v.rend() ; iter++) printf("%d ",*iter);
 
    return 0;
}