[백준 13913] 숨바꼭질 4

 

 

 BFS 문제. 같은 시리즈인 숨바꼭질 3 문제를 풀고, 뭔가 아쉬워서 다음 넘버링이 있는지 찾아보니 있어서 이것도 풀었다. 문제가 단순해서 그냥 BFS를 사용하면 바로 풀린다. 숨바꼭질 3 같은 경우에는 순간이동에 걸리는 시간만 0초라서 우선순위 큐와 다익스트라를 이용했었는데, 이 문제는 모두 같은 시간이 걸리므로 일반적인 큐와 BFS를 사용했다.

 이동 경로를 출력해야 하는 부분이 있어서, 직전 노드를 저장해두는 prev 배열을 따로 선언해서 BFS 내에서 처음 노드 방문 시에 함께 갱신해주었다.

 

 사실 위 문제를 풀면서 다른 부분에서 애를 좀 먹었는데, prev 배열을 이용해서 최종 경로를 역추적 하는 과정에서 살짝 미스가 있어서 원인을 한참 찾았다.

 혹시 본인이 작성한 BFS를 사용하는 본 로직에는 전혀 이상이 없는데, 이상하게 메모리 초과가 나거나 틀린다면 경로 역추적하는 부분을 확인해보면 좋을 것 같다. 특히 n과 k가 같을 때.

 

#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321 

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<bool> isVisited(100001, false);
    vector<int> prev(100001, -1);
    queue<pair<int, pair<int, int> > > q; //{cost, {position, prev}}

    q.push({0, {n, n}});

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

        if(isVisited[cur.second.first]) continue;
        prev[cur.second.first] = cur.second.second;
        if(cur.second.first == k) {
            cout << cur.first << "\n";
            break;
        }
        isVisited[cur.second.first] = true;
        
        int nextPosition[3] = {cur.second.first*2, cur.second.first+1, cur.second.first-1};

        for(int next : nextPosition) {
            if(0<=next && 100000>=next) {
                q.push({cur.first+1, {next, cur.second.first}});
            }
        }
    }

    vector<int> route;
    int ind = k;
    while(true) {
        route.push_back(ind);
        if(ind==n) break;
        ind = prev[ind];
    }

    for(int i=route.size()-1; i>=0; i--) {
        cout << route[i] << " ";
    }
}