[백준/C++] 13913번 숨바꼭질 4

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

13913번: 숨바꼭질 4

 

 

문제풀이

 

숨바꼭질 시리즈 문제, 일차원 직선에서의 BFS로 시작점(N)에서 동생(K)까지의 최단거리를 구하는 문제이다.

 

다른 숨바꼭질 문제와 다르게 수빈이의 경로도 출력해주어야 하기 때문에 dist배열을 2차원으로 선언하여 점마다 현재 점의 직전 점을 저장하였다. 

 

마지막에 동생(K)에 도착하면 K부터 N까지 경로를 역으로 추적하여 벡터에 저장 후 순서대로 출력했다.

 

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int dist[200001][2]; //직전의 점을 저장하기 위해 2차원으로 선언했다.

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n,k;
    cin>>n>>k;

    queue<int> q;
    q.push(n);
    dist[n][0] = 1;
    dist[n][1] = n;

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        if(cur == k){
            cout<<dist[cur][0]-1<<"\n";
            vector<int> v;
            
            for(int i=cur; i != n; i = dist[i][1]){ //K부터 N까지 역으로 저장
                v.push_back(i);
            }
            
            v.push_back(n);

            for(int i = v.size()-1; i>=0; i--){ //역순으로 출력
                cout<<v[i]<<" ";
            }
        }

        int nm = cur - 1;
        if(nm>=0 && nm<=200000 && !dist[nm][0]){
            dist[nm][0] = dist[cur][0] + 1;
            dist[nm][1] = cur;
            q.push(nm);
        }

        int np = cur + 1;
        if(np>=0 && np<=200000 && !dist[np][0]){
            dist[np][0] = dist[cur][0] + 1;
            dist[np][1] = cur;
            q.push(np); 
        }

        int nd = cur*2;
        if(nd>=0 && nd<=200000 && !dist[nd][0]){
            dist[nd][0] = dist[cur][0] + 1;
            dist[nd][1] = cur;
            q.push(nd); 
        }
    }

    return 0;
}

 

 

결과