백준 1854번 [K번째 최단경로 찾기](C++) -yes6686- 티스토리

백준 문제 풀이: 1854 [K번째 최단경로 찾기]

---

문제 링크: https://www.acmicpc.net/problem/1854

문제 설명:

가중치가 있는 방향 그래프에서, 시작 노드에서 각 노드로 가는 K번째 최단 경로의 가중치 합을 구하는 문제입니다.

• 각 노드에 대해 정확히 K번째로 작은 경로 비용을 출력해야 합니다.
• K번째 최단 경로가 존재하지 않으면 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;

vector<pair<int, int>> graph[1001]; // 인접 리스트로 그래프 표현
priority_queue kShortest[1001]; // 각 노드의 K번째 최단 경로 저장
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 다익스트라용 우선순위 큐

void dijkstra(int start, int n, int k) {
    pq.push({0, start}); // 시작 노드로 가는 비용은 0
    while (!pq.empty()) {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        for (auto [nextCost, next] : graph[cur]) {
            int newCost = cost + nextCost;

            // K번째 최단 경로를 업데이트
            if (kShortest[next].top() > newCost) {
                kShortest[next].push(newCost);
                kShortest[next].pop();
                pq.push({newCost, next});
            }
        }
    }
}

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

    int n, m, k; // 노드 수, 간선 수, K번째 최단 경로
    cin >> n >> m >> k;

    // K번째 최단 경로를 위해 각 노드에 INF로 초기화된 최대 힙 생성
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            kShortest[i].push(INF);
        }
    }

    // 그래프 입력
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
    }

    // 시작 노드 설정
    kShortest[1].push(0);
    kShortest[1].pop();

    // 다익스트라 알고리즘 실행
    dijkstra(1, n, k);

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        if (kShortest[i].top() == INF) {
            cout << -1 << '\n';
        } else {
            cout << kShortest[i].top() << '\n';
        }
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 다익스트라 알고리즘을 변형하여 각 노드로의 K번째 최단 경로를 계산합니다. 각 노드에 대해 우선순위 큐를 유지하여 K개의 최단 경로를 저장합니다.
• 구현 세부사항:
  • kShortest: 각 노드의 K번째 최단 경로를 저장하는 최대 힙
  • 다익스트라 탐색 중, 새로운 경로 비용이 현재 K번째 최단 경로보다 작을 경우 우선순위 큐를 업데이트합니다.
  • K번째 최단 경로가 없는 경우 -1을 출력합니다.
• 시간 복잡도 분석:
  • 다익스트라 탐색: O(E log k), 여기서 E는 간선의 수
  • K개의 경로를 유지하기 위한 우선순위 큐 연산: O(log k)
  전체 시간 복잡도는 O(E log k)입니다.

---

결과

각 노드에 대해 K번째 최단 경로를 정확히 출력합니다. 그래프 탐색을 효율적으로 수행하며, 우선순위 큐를 활용해 경로의 우선순위를 유지합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!