BOJ : 13913 숨바꼭질4

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

기존 1697 숨바꼭질 과 같은 문제지만 추가로 지나온 경로를 출력을 요구한다는 점에서 차이가 있다.

처음에는 queue에 경로 벡터를 추가해서 노드마다 경로 값을 가지는 무식한 짓을 벌였다.

어처피 목적지에 도달하는 최소 경로중 하나만 출력하면 되기 때문에 배열 하나로 지나온 경로를 관리하는 방법으로 AC를 얻었다.

visited[다음 경로] = 현재 경로  가 된다. 

그리고 목적이에 도달했을 때 목적지에서 출발지까지 뒤로 탐색해 vector에 push한 다음 다시 출력하게 되면 원하는 경로가 출력될 것이다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int px[2]={1,-1};
int N,K,cnt=0;
int visited[100002];
queue<int> q;
int main(){
    scanf("%d%d",&N,&K);
    q.push(N);
    for(int i=0;i<100001;i++)
        visited[i]=-1;
    
    visited[N]=N;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int x = q.front();
            q.pop();
            if(x==K){
                printf("%d\n",cnt);
                vector<int> v;
                int pre = K;
                while(pre!=N){
                    v.push_back(pre);
                    pre = visited[pre];
                }
                printf("%d",N);
                for(int i=v.size()-1;i>=0;i--)
                    printf(" %d",v[i]);
                
                return 0;
            }
            for(int i=0;i<3;i++){
                int nx;
                if(i==2) nx = 2*x;
                else nx = x + px[i];
                if(nx > 100000 || nx < 0) continue;
                if(visited[nx]!=-1) continue;
                visited[nx]=x;
                q.push(nx);
            }
        }
        cnt++;
    }
}