백준 13913번 숨바꼭질 4 - C++ 풀이

---

 

1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다.
2. BFS 과정에서 이전 노드를 기록하여 경로를 구할 수 있도록 한다.

 

1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다.

 수 하나를 노드 하나라고 생각하고, n번 노드와 [n+1, n-1, 2n]번 노드는 간선으로 이어져있다고 생각하면 된다. BFS를 이용하여 N번 노드에서 K번 노드까지의 거리를 구한다.

 이때 노드 번호의 범위를 [0, 200000]으로 제한할 수 있다. N, K의 범위가 100,000이므로 거리의 최댓값은 100,000이다. 그런데 200,000보다 큰 노드의 경우 더 작아지는 방법은 -1 밖에 없기 때문에 최소 100,000번의 연산을 해야 K로 갈 수 있다. 따라서 200,000을 넘어가는 수는 고려하지 않아도 된다.

 

2. BFS 과정에서 이전 노드를 기록하여 경로를 구할 수 있도록 한다.

 마지막에 경로까지 출력해야 하므로 이전 노드를 기록해두어 K에서 N까지 역추적하면서 경로를 출력할 수 있도록 한다.

 

반응형

---

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

using namespace std;

int N, K;

void BFS() {
    vector<int> visit(200001, -1);
    vector<int> before(200001, -1);
    queue<int> q;
    
    visit[N] = 0;
    q.push(N);
    
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        
        if (curr == K) {
            vector<int> route;
            
            while (curr != -1) {
                route.push_back(curr);
                curr = before[curr];
            }
            
            reverse(route.begin(), route.end());
            
            cout << route.size()-1 << "\n";
            for (auto node: route) cout << node << " ";
            
            return;
        }
        
        int nexts[] = {curr-1, curr+1, curr*2};
        for (auto next: nexts) {
            if (next < 0 || next > 200000) continue;
            if (visit[next] != -1) continue;
            
            visit[next] = visit[curr] + 1;
            before[next] = curr;
            q.push(next);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    
    BFS();
    
    return 0;
}