n개의 도시가 m개의 항공편으로 연결되어 있다고 가정해 봅시다. 각 항공편은 출발지 u에서 도착지 v까지 가격 w로 운항됩니다. 모든 도시와 항공편 정보, 그리고 출발 도시 src와 목적지 dst가 주어졌을 때, 우리의 과제는 최대 k번의 경유(스톱)를 허용하면서 src에서 dst까지 도달하는 최저 가격을 찾는 것입니다. 만약 그러한 경로가 존재하지 않는다면 -1을 반환해야 합니다.
예를 들어 입력이 n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1이라면 출력은 200이 됩니다.
이는 직행 노선(0 → 2)의 비용이 500이지만, 한 번 경유하는 노선(0 → 1 → 2)의 총비용은 100 + 100 = 200으로 더 저렴하기 때문입니다.
문제 해결 접근 방식
이 문제는 다익스트라(Dijkstra) 알고리즘을 변형하여 해결할 수 있습니다. 일반적인 다익스트라와 달리, 경유 횟수 제한이 있으므로 각 도시에 도달할 때의 경유 횟수별 최소 비용을 함께 관리해야 합니다. 해결 단계는 다음과 같습니다.
- 노드(node), 거리(dist), 비용(cost)을 저장할 수 있는 Data 구조체를 생성합니다.
- 2차원 배열 cost를 정의합니다.
- cost := (n + 1) × (K + 10) 크기의 2차원 배열로, 모든 값을 무한대(INF)로 초기화합니다.
- 그래프 인접 리스트 graph를 정의합니다.
- i := 0부터 flights 크기 미만까지 반복하면서 다음을 수행합니다.
- u := flights[i][0] (출발 도시)
- v := flights[i][1] (도착 도시)
- graph[u]의 끝에 { v, flights[i][2] }를 삽입합니다.
- Data 타입의 우선순위 큐(priority queue) q를 정의합니다.
- q에 Data(src, 0, 0)을 삽입하고, cost[src][0] := 0으로 설정합니다.
- ans := -1로 초기화합니다.
- q가 빌 때까지 다음을 반복합니다.
- temp := q의 최상단 요소
- curr := temp.node
- q에서 해당 요소를 제거(pop)
- dist := temp.dist
- 만약 curr이 dst와 같다면 temp.cost를 반환합니다.
- dist를 1 증가시킵니다.
- dist > K + 1이면 다음 반복으로 건너뜁니다.
- i := 0부터 graph[curr] 크기 미만까지 반복하면서 다음을 수행합니다.
- neighbour := graph[curr][i][0]
- cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]이면
- cost[neighbour][dist] := cost[curr][dist - 1] + graph[curr][i][1]로 갱신
- q에 Data(neighbour, dist, cost[neighbour][dist])를 삽입
- 루프가 종료되면 -1을 반환합니다.
여기서 dist는 실제로 '사용한 항공편 수'를 의미하며, K번 경유는 곧 최대 K+1개의 항공편 사용을 의미하므로 dist가 K+1을 초과하면 더 이상 탐색하지 않습니다.
예제 코드 (C++)
아래 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct Data{
int node, dist, cost;
Data(int a, int b, int c){
node = a;
dist = b;
cost = c;
}
};
struct Comparator{
bool operator() (Data a, Data b) {
return !(a.cost < b.cost);
}
};
class Solution {
public:
vector<vector<int>> cost;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
cost = vector<vector<int> >(n + 1, vector<int>(K + 10, INT_MAX));
vector<vector<int> > graph[n];
for (int i = 0; i < flights.size(); i++) {
int u = flights[i][0];
int v = flights[i][1];
graph[u].push_back({ v, flights[i][2] });
}
priority_queue<Data, vector<Data>, Comparator> q;
q.push(Data(src, 0, 0));
cost[src][0] = 0;
int ans = -1;
while (!q.empty()) {
Data temp = q.top();
int curr = temp.node;
q.pop();
int dist = temp.dist;
if (curr == dst)
return temp.cost;
dist++;
if (dist > K + 1)
continue;
for (int i = 0; i < graph[curr].size(); i++) {
int neighbour = graph[curr][i][0];
if (cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]) {
cost[neighbour][dist] = cost[curr][dist - 1] + graph[curr][i][1];
q.push(Data(neighbour, dist, cost[neighbour][dist]));
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,100},{1,2,100},{0,2,500}};
cout << (ob.findCheapestPrice(3, v, 0, 2, 1));
}입력
3, {{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1출력
200
정리
이 알고리즘은 우선순위 큐를 활용해 현재까지의 누적 비용이 가장 낮은 상태부터 탐색하며, 동시에 경유 횟수를 상태의 일부로 포함시켜 K번 환승 제약 조건을 처리합니다. 덕분에 단순히 최단 거리만 보는 다익스트라와 달리, 환승 제한이 있는 현실적인 항공권 가격 문제를 정확하게 해결할 수 있습니다. 시간 복잡도는 O(E × K log V) 수준으로, 도시 수와 항공편 수가 적당한 범위에서 효율적으로 동작합니다.