C++ 코딩테스트 강좌, K번째 최단 경로 찾기

안녕하세요! 이번 강좌에서는 알고리즘 문제 중 하나인 “K번째 최단 경로 찾기”에 대해 이야기하겠습니다. 이 문제는 실전 코딩 테스트에서 자주 등장하며, 그래프와 최단 경로 알고리즘에 대한 깊은 이해를 요구합니다. 이 문제를 통해 다익스트라 알고리즘과 우선순위 큐를 활용하는 방법을 배워보겠습니다.

문제 설명

주어진 그래프에서 두 정점 A와 B 사이의 K번째 최단 경로의 길이를 알아내는 문제입니다. 최단 경로는 다수의 경로 중에서 가장 짧은 길이를 가진 경로를 의미하며, K번째 최단 경로란 최단 경로보다 길이가 더 길면서 가장 짧은 경로를 의미합니다. 동일한 경로가 여러 번 존재할 수 있습니다.

입력

정점의 개수 N (1 ≤ N ≤ 400)
간선의 개수 M (1 ≤ M ≤ 100,000)
K (1 ≤ K ≤ 3000)
각 간선 정보 (시작 정점, 종료 정점, 가중치)
정점 A와 B

출력

K번째 최단 경로의 길이를 출력합니다. 만약 K번째 최단 경로가 존재하지 않는다면 -1을 출력합니다.

문제 접근 방법

이 문제를 풀기 위해서는 K번째 최단 경로를 찾는 방법에 대해 고민해야 합니다. 일반적인 다익스트라 알고리즘은 최단 경로를 찾는 데 효과적이지만, K번째 경로를 찾기 위해서는 추가적인 조치를 취해야 합니다.

해당 문제를 해결하기 위해 사용하는 자료구조는 다음과 같습니다:

우선순위 큐 (Priority Queue): 최소 값이 우선으로 처리되도록 합니다.
벡터 (Vector): 그래프 구조를 표시하는 데 사용합니다.

알고리즘 단계

그래프를 입력받아 인접 리스트(adjacent list)로 표현합니다.
각 정점에 대한 경로 리스트를 우선순위 큐에 저장합니다.
시작 정점으로부터 다익스트라 알고리즘을 사용하여 K번째 최단 경로를 찾습니다.
경로 리스트에서 K번째로 작은 값을 찾아 출력합니다.

C++ 코드 구현


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

using namespace std;

const int INF = 1e9;  // 무한대 정의

struct Edge {
    int to, weight;
};

int N, M, K;
vector<Edge> graph[401];
vector<int> dist[401];  // 각 정점의 K번째 최단 경로 길이

void findKthShortestPath(int start, int end) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(0, start, 0));  // (길이, 현재정점, 경로 수)
    
    while (!pq.empty()) {
        auto [length, current, count] = pq.top();
        pq.pop();
        
        if (count >= K) continue; // K개 이상의 경로를 탐색할 필요 없음
        dist[current].push_back(length);
        
        for (auto &edge : graph[current]) {
            int next = edge.to;
            int weight = edge.weight;
            pq.push(make_tuple(length + weight, next, count + 1));
        }
    }
}

int main() {
    cin >> N >> M >> K; // 정점, 간선, K 가져오기
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w}); // 간선 추가
    }

    int A, B;
    cin >> A >> B;

    findKthShortestPath(A, B);
    
    if (dist[B].size() < K) {
        cout << -1 << endl; // K번째 최단 경로가 없으면 -1 반환
    } else {
        cout << dist[B][K-1] << endl; // K번째 최단 경로 출력
    }

    return 0;
}

결론

이번 강좌에서는 K번째 최단 경로 찾기라는 문제를 통해 그래프 탐색의 다양한 방법과 우선순위 큐를 이용한 효율적인 경로 탐색 방법을 살펴보았습니다. 이 문제를 해결하는 과정에서 다익스트라 알고리즘의 변형을 통해 K번째 경로를 찾는 방법에 대해 배울 수 있었습니다. 이러한 문제들에 대한 이해는 실제 코딩 테스트에서 높은 점수를 받을 수 있는 기회를 제공할 것입니다.

여러분도 이 문제를 연습하면서 그래프 탐색에 대한 이해를 높이고, 코딩 실력을 한 단계 끌어올리길 바랍니다. 감사합니다!

문제 설명

입력

출력

문제 접근 방법

알고리즘 단계

C++ 코드 구현

결론

관련