[BOJ] 13913번 : 숨바꼭질4 (C++)

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

13913번: 숨바꼭질 4

 

이 문제는 1697번:숨바꼭질 문제와 같은 문제인데, 최소 경로만 출력하면 되는 문제이다.

1차원에서의 BFS이며, 보통의 BFS는 상하좌우에 대한 포문을 돌았지만 이 문제는 이동가능한 값들로 포문을 돌게 된다.

최소 경로를 출력하기 위해선 경로를 저장하며 BFS를 돌아야 한다. 

그래서 way라는 배열을 추가해주고, 각 자리의 값은 어느 위치에서 이동을 해온 것인지를 저장해주었다.

문제에 나와있는 예제1 출력은 '5 10 9 18 17' 이다. 이 예제에 대한 way안에 값은 다음과 같이 된다. (해당 경로를 제외한 way값은 표시하지 않았음)

 

					5				10
way[0]	way[1]	way[2]	way[3]	way[4]	way[5]	way[6]	way[7]	way[8]	way[9]

5							18	9
way[10]	way[11]	way[12]	way[13]	way[14]	way[15]	way[16]	way[17]	way[18]	way[19]

처음 시작하는 곳은 자기자신을 넣어주어 시작한 곳이라는 표시를 해둔다. 그리고 자신이 어느 좌표로부터 온 것인지를 표시해주면 된다. 

BFS를 다 돌리고 나서 경로를 찾아가기 위해선 거꾸로 끝난 시점에서부터 경로를 찾아간다.

way[17]에서 18 값을 얻고, way[18]에서 9를 얻고, way[9]에서 10을 얻고, way[10]에서 5를 얻고 5에서 자기자신 값을 얻으면 경로를 모두 찾은 것이다. 

이런 식으로 경로를 거꾸로 탐색하기 때문에 찾은 값을 거꾸로 출력해줄 필요가 있다.

그래서 deque를 이용하여 얻은 값을 앞에 추가해주면 아주 편리하게 구현이 가능하다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;

int n,k;
int dist[100005];
int way[100005];
queue<int> q;

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

    cin>>n>>k;

    fill(dist, dist+100005, -1); //-1로 초기화
    
    way[n]=n; //시작의 의미로 n 저장
    dist[n]=0; //n에서 시작
    q.push(n);

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

        if(cur==k) {
            cout<<dist[k]<<'\n';
            break;
        }
        for(auto i : {cur+1, cur-1, cur*2}){
            if(i<0||i>100000) continue;
            if(dist[i]!=-1) continue;

            way[i]=cur;
            dist[i]=dist[cur]+1;
            q.push(i);
        }
    }

    //경로는 여러 개일 수 있어서 input 예제와 다르게 나왔지만 정답임 
    //스페셜져지 : 답이 여러 가지가 될 수 있어 그 모두를 답으로 채점하기 위한 특별한 채점 프로그램이 들어가 있다는 뜻
    
    //거꾸로 17부터 5까지 가는 경로로 거꾸로 나오게 됨 (k에서 n으로 감)
    //그래서!! deque를 이용하면 매우 편하게 구현가능함
    deque<int> track;
    track.push_back(k);

    while(track.front() != n){
        track.push_front(way[track.front()]);
    }
    for(auto i : track) cout<<i<<" ";

    return 0;
}

 

회고) 

way라는 배열을 만들고 여기에 지나왔던 값을 저장하는 것까지는 아이디어를 낼 수 있었다. 

그리고 나서 경로를 출력하려고 했을 때, 이미 다 쓰고나서 쓸모가 없어졌다고 생각한 dist배열에다가 값을 하나하나 저장하고 거꾸로 읽으려고 했었다.. 

이번 문제의 핵심 중 하나는 값을 거꾸로 읽으니 읽은 값을 앞에다가 저장하기 위한 deque를 생각해내는 것인거 같다. 

값을 저장하고 저장한 값을 거꾸로 읽어야 한다면 애초에 새로운 값을 앞에서부터 추가해주면 되었다. 

다음부터는 값을 거꾸로 읽어야한다면 deque를 꼭 생각해내야겠다.