[P4] 백준 1854번 K번째 최단경로 찾기 C++ 다익스트라, 우선순위 큐

리뷰

 

https://www.acmicpc.net/problem/1854

다익스트라 + 우선순위 큐를 활용해 각 노드별 k번째 최단 경로를 관리하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• k : 구하고자 하는 최단 경로의 수를 정의할 변수
• Edge : 간선 정보를 정의할 구조체
• edges : 간선 정보를 인접 리스트로 저장할 Edge타입 벡터 배열
• Pos : 현재 정보를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

void dijkstra() {
    priority_queue<Pos> pq;
    pq.push({ 1, 0 });
    vector<priority_queue<int>> dist(n + 1);

    while (!pq.empty()) {
        Pos pos = pq.top(); pq.pop();
        int cn = pos.cn, cv = pos.cv;

        if (dist[cn].size() >= k && dist[cn].top() <= cv) continue;
        dist[cn].push(cv);

        if (dist[cn].size() > k) dist[cn].pop();

        for (const Edge& edge : edges[cn]) {
            int nn = edge.nn, nc = cv + edge.nv;

            if (dist[nn].size() < k || (dist[nn].size() == k && dist[nn].top() > nc)) {
                pq.push({ nn, nc });
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i].size() < k) {
            cout << -1 << "\n";
        }
        else {
            while (dist[i].size() > k) dist[i].pop();
            cout << dist[i].top() << "\n";
        }
    }
}

 

각 노드를 순회하며 방문한 누적 가중치를 저장하기 위한 함수

 

 

문제풀이

1. n, m, k값을 입력 받고, m개의 간선 정보를 입력 받아 edges를 초기화 해준다.
2. dijkstra함수를 호출하고, Pos타입의 우선순위 큐 pq를 초기화 및 시작 노드 1, 가중치 0을 push한다.
3. n+1개의 일반적인 정수형 내림차순 우선순위 큐 벡터를 초기화 한다.
4. pq가 빌때까지 while루프를 순회하며 매 루프마다 요소를 한개씩 꺼내 변수 cn, cv에 파싱해 준다.
5. 기저 조건으로 dist[cn]의 크기가 k이상이면서 dist[cn]의 최대값이 cv이하일 경우 continue처리해 준다.
6. dist[cn]의 크기가 k보다 클 경우 dist[cn]에서 최대값을 하나 빼내어 준다.
7. cn의 인접 리스트를 순회하며 이동할 노드와 누적 가중치를 변수 nn, nv에 파싱해 준다.
8. dist[nn]의 크기가 k보다 작거나 k와 같으면서 최대값이 nv보다 크다면 pq에 nn, nv를 push해준다.
9. while루프가 종료된 후 1~n번 노드를 순회하며 dist[i]의 크기가 k보다 작다면 -1을 출력해 준다.
10. k보다 크다면 요소를 pop하여 k개까지 맞춰준 후 dist[i]의 top에 있는 요소를 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 각 노드별 우선순위 큐에는 최대 k개 까지의 요소가 들어가 있을 수 있다.
2. k번째 최단 경로는 최대값 우선순위 큐의 top에 해당하므로 k개보다 적다면 -1을, 아니라면 top값을 출력하면 된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 1001;
int n, m, k;
struct Edge {
    int nn, nv;
};
vector<Edge> edges[N];
struct Pos {
    int cn, cv;
    bool operator<(const Pos& other) const {
        return cv > other.cv;
    }
};

void dijkstra() {
    priority_queue<Pos> pq;
    pq.push({ 1, 0 });
    vector<priority_queue<int>> dist(n + 1);

    while (!pq.empty()) {
        Pos pos = pq.top(); pq.pop();
        int cn = pos.cn, cv = pos.cv;

        if (dist[cn].size() >= k && dist[cn].top() <= cv) continue;
        dist[cn].push(cv);

        if (dist[cn].size() > k) dist[cn].pop();

        for (const Edge& edge : edges[cn]) {
            int nn = edge.nn, nv = cv + edge.nv;

            if (dist[nn].size() < k || (dist[nn].size() == k && dist[nn].top() > nv)) {
                pq.push({ nn, nv });
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i].size() < k) {
            cout << -1 << "\n";
        }
        else {
            while (dist[i].size() > k) dist[i].pop();
            cout << dist[i].top() << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({ b, c });
    }

    dijkstra();
}