View in English →

Code › algorithm-study

리트코드 787 - Cheapest Flights Within K Stops

환승 제한(K) 조건이 있을 때의 벨만-포드 변형 알고리즘

algorithmleetcodebellman-forddijkstracpplearning

최단 경로(최소 비용) 문제를 풀 때 보통 다익스트라(Dijkstra) 알고리즘을 먼저 공부하게 된다. 그래서 처음에는 다익스트라로 접근하는 방식을 먼저 살펴보고 있었는데, 이 문제 특성상 일반적인 최단 거리 알고리즘을 그대로 쓰기보다 벨만-포드를 살짝 변형한 방식이 더 어울리는 문제였다.

문제 링크 & 설명

  • 문제 링크: 787. Cheapest Flights Within K Stops
  • 요약: n개의 도시와 각 도시를 잇는 비행편의 가격이 주어질 때, 출발지(src)에서 목적지(dst)까지 가는 가장 저렴한 가격을 찾는 문제다. 단, 최대 K번까지만 환승(Stops)할 수 있다는 제약 조건이 붙는다. 즉, 비행기를 탈 수 있는 총 횟수가 최대 K + 1번으로 제한된다.

접근 방법

다익스트라 방식을 고려해 보았지만, 다익스트라는 “비행기를 몇 번 탔는지” 카운트하는 제약 조건을 처리하기가 조금 까다롭다. 누적 비용이 가장 싼 경로를 우선순위 큐로 먼저 파고들기 때문에, 나중에 뒤늦게 환승 횟수가 초과했음을 알게 되었을 때 처리가 복잡해지기 때문이다.

반면 모든 노선표를 처음부터 끝까지 통째로 한 바퀴 훑는 행위를 ‘한 회차(라운드)‘로 정의하는 벨만-포드 방식을 적용하면 흐름이 훨씬 깔끔해진다.

  • 1회차 순회: 출발지에서 비행기 1번만 타서 갈 수 있는 도시들의 최소 비용 계산
  • 2회차 순회: 1회차 때 찾아둔 도시들을 발판 삼아, 비행기 2번(환승 1번)으로 갈 수 있는 도시들 계산

이런 식으로 라운드를 진행하면 딱 K + 1번만 루프를 돌고 종료하면 되므로 환승 제한 조건을 아주 직관적으로 제어할 수 있다. 원래 벨만-포드는 시간 복잡도가 다소 무거운 편이지만, 이 문제에서는 K가 도시 수에 비해 작은 숫자로 주어지기 때문에 오버헤드가 큰 우선순위 큐를 쓰는 다익스트라 변형보다 오히려 이 방식이 더 깔끔하겠다는 생각이 들었다.

트러블 슈팅

한 회차 안에서 결과가 미리 누적되는 문제

하나의 최단 거리 배열(dist)만 사용해서 1회차 순회를 돌 때 구조적인 버그가 생길 수 있었다. 1회차 안에서 순서대로 노선들을 돌다 보면, 아직 탐색하지 않은 노선 중에 ‘방금 막 업데이트된 도시’를 출발지로 하는 노선이 존재할 수 있다.

그렇게 되면 원래는 다음 회차에 계산되어야 할 노선이 당장 1회차 안에서 연쇄적으로 계산되어 버린다. 결과적으로 1회차 안에서 경유 횟수가 하나 더 늘어난 상태로 잘못 누적되는 현상이 발생하는 것이다.

[해결책]: 이전 회차까지 안전하게 완성되어 있던 기준 지도를 dist1, 이번 회차의 계산 결과를 새로 받아 적을 임시 지도를 dist2로 나누어 저장하기로 했다. 이번 회차 중에 갱신되는 임시 값은 오직 dist2에만 적히기 때문에, 계산이 실시간으로 번지는 문제를 완전히 차단할 수 있다. 한 회차가 끝나면 dist2의 결과를 dist1에 엎어치며(dist1 = dist2) 다음 회차로 넘어간다. (엎어치는 비용도 비용이긴 하다)

복잡도 분석

이 문제에서 벨만-포드 변형 알고리즘이 정량적으로 어떤 시간 복잡도와 공간 복잡도를 가지는지 분석해 보았다.

1. 시간 복잡도

  • 벨만-포드 변형 (이번 풀이): O(K × E)
    • 환승 제한 횟수 조건에 따라 메인 루프를 정확히 K + 1번 수행한다. 매 라운드마다 모든 노선(간선, E)을 처음부터 끝까지 한 바퀴씩 순회하므로 최종 시간 복잡도는 O(K × E)가 된다.
    • 복잡한 자료구조나 정렬 오버헤드 없이, 정해진 라운드 횟수만큼 노선표 배열을 정직하게 순회하므로 직관적이고 안정적으로 동작한다.

2. 공간 복잡도

  • 벨만-포드 변형 (이번 풀이): O(V)
    • 각 도시의 최소 비용을 저장하기 위해 크기가 V(도시 수)인 1차원 배열 딱 2장(dist1, dist2)만 사용한다.
    • 라운드가 끝날 때 배열을 복사하는 O(V) 시간 비용이 들긴 하지만, 사용하는 총 메모리 공간은 환승 제한 횟수(K)나 전체 노선 수(E)의 크기와 상관없이 오직 도시 수(V)에만 비례하므로 메모리 측면에서 효율적이다.

최적화 코드

위의 흐름을 바탕으로 구현하여 최종적으로 통과한 C++ 코드

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // 크기 n, 초기값 INT_MAX로 올바르게 세팅
        vector<int> dist1(n, INT_MAX);
        vector<int> dist2(n, INT_MAX);
        
        // 출발지의 비용은 0원으로 초기화
        dist1[src] = 0;
        dist2[src] = 0;

        int count = k + 1;
        while (count--) {
            for (auto& flight: flights) {
                int from = flight[0];
                int to = flight[1];
                int price = flight[2];
                
                // 이전 지도(dist1)에서 도달할 수 있었던 도시만 디딤돌로 삼는다
                if (dist1[from] < INT_MAX) {
                    int newPrice = dist1[from] + price;
                    // 이번 지도(dist2)의 기존 값보다 더 저렴할 때만 최솟값 갱신
                    if (newPrice < dist2[to]) {
                        dist2[to] = newPrice;
                    }
                }
            }
            // 라운드가 끝났으므로 최신 지도를 이전 지도로 엎어친다.
            dist1 = dist2;
        }
        
        // 최종 목적지가 여전히 INT_MAX라면 갈 수 없는 곳이므로 -1 리턴
        return dist2[dst] == INT_MAX ? -1 : dist2[dst];
    }
};

요약 및 회고 문제의 환승 제한(K) 조건의 특징을 파악하고 그에 맞는 알고리즘의 메커니즘을 고민해 볼 수 있었는데, 나중에는 gemini와 함께하며 문제를 더욱 깊이 이해해보는 좋은 시간이 되었다.