[BOJ] 13913 - 숨박꼭질 4

문제

숨박꼭질 4

코드

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

using namespace std;

int N, M, T;
bool visited[200001];
int parent[200001];

vector<int> path;

int main(void){
    cin >> N >> M;

    queue<int> q;
    q.push(N);
    
    while (!q.empty()){
        int pos = q.front();
        q.pop();
        
        if (pos == M) {
            int x = pos;
            while (x != N){
                path.push_back(x);
                x = parent[x];
            }
            path.push_back(x);
            cout << path.size()-1 << endl;
            break;
        }

        if (0 <= pos-1 and pos-1 <= 200000 and !visited[pos-1]) {
            parent[pos-1] = pos;
            visited[pos-1] = true;            
            q.push(pos-1);
        }
        if (0 <= pos+1 and pos+1 <= 200000 and !visited[pos+1]) {
            parent[pos+1] = pos;
            visited[pos+1] = true; 
            q.push(pos+1);
        }
        if (0 <= pos*2 and pos*2 <= 200000 and !visited[pos*2]) {
            parent[pos*2] = pos;
            visited[pos*2] = true;
            q.push(pos*2);
        }
    }
    for (int i = path.size()-1; i >= 0; i--) cout << path[i] << " ";
    return 0;
}

접근

위치를 찾게되는 가장 빠른 시점을 알아야 하기 때문에 bfs를 선택했다. 고민했던 부분은 bfs이지만 지나온 경로를 알아야하기 때문에 이를 어떻게 처리할지 였다. bfs탐색의 경우 이미 방문한 곳은 다시 가지 않아도 되고 때문에 왔던 곳들을 역추적할 수 있다면 이것을 뒤집으면 경로로 확인할 수 있었다. 이를 위해서 parent 배열을 사용하였다.

parent[x] = y; => x의 이전 경로는 y

이를 통해서 찾는 위치에 도달했을 경우 이제껏 방문한 위치를 역추적해서 경로를 확인할 수 있었다.