[BOJ 27011] Part Acquisition

백준 문제 링크

🔍 문제 분석

• 문제의 설명을 읽어보면, 1번 노드에서 출발하여 K번 노드에 이르는 최단 경로를 탐색하는 문제로 이해할 수 있다.
• 문제에서 주어진 그래프는 모든 노드의 가중치가 1인 유향 그래프이므로, BFS알고리즘을 활용한다면 최단 경로를 쉽게 탐색할 수 있다.
• 출력은 최단 경로의 길이뿐 아니라, 최단 경로를 구성하는 노드의 번호를 요구한다. BFS를 진행하며 각 노드에 대하여 이전 노드의 번호를 기록한 뒤 마지막에 역순으로 거슬러 올라가며 노드의 번호를 탐색한다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 50'000;

int N, K, p[MAX + 1];
vi graph[MAX + 1];

void bfs(int node) {
    queue<int> q;
    q.push(node);
    p[node] = 1;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (auto next : graph[curr]) {
            if (p[next]) continue;
            q.push(next);
            p[next] = curr;
        }
    }
}

int main() {
    fastio;

    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    bfs(1);
    if (p[K]) {
        vi ans;
        while (true) {
            ans.push_back(K);
            if (p[K] == K) break;
            K = p[K];
        }
        cout << ans.size() << "\n";
        for (int i = ans.size() - 1; i >= 0; --i) {
            cout << ans[i] << "\n";
        }
    } else {
        cout << -1;
    }
}

📝 코드 설명

🔧 트러블 슈팅

📚 참고자료