LeetCode 787 - Cheapest Flights Within K Stops (Medium)

출처: https://leetcode.com/problems/cheapest-flights-within-k-stops/

// LeetCode 787 - Cheapest Flights Within K Stops (Medium)
// https://leetcode.com/problems/cheapest-flights-within-k-stops/
// (관련 문제: LeetCode 743 다익스트라 / 같은 발상의 수업 문제: 백준 14497 주난의 난 — 라운드 BFS)

// 문제 설명
// n개 도시와 항공편 flights[i] = [from, to, price] 가 주어진다.
// src 에서 dst 까지 "경유 k번 이하"로 갈 때의 최소 비용을 구하고, 그런 경로가 없으면 -1.

// 제약 조건
// 2 <= n <= 100, 0 <= flights.length <= n * (n - 1) / 2   (간선 0개인 입력도 허용)
// 0 <= from, to < n, from != to, 1 <= price <= 10^4       (가격은 항상 양수)
// 0 <= src, dst, k < n, src != dst

// Example
// Input : n=4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0->3, k=1
// Output: 700     (0-1-2-3 이 400으로 더 싸지만 경유 2번이라 실격 → 0-1-3)
//
// Input : n=3, [[0,1,100],[1,2,100],[0,2,500]], 0->2, k=1
// Output: 200     (경유 1번 허용이라 0-1-2)
//
// Input : n=3, [[0,1,100],[1,2,100],[0,2,500]], 0->2, k=0
// Output: 500     (직항만 가능)
// → 같은 그래프에서 k만 바꿔 답이 갈린다. 답은 그래프만의 함수가 아니라 (그래프, k)의 함수다.

// 접근 — 라운드를 k+1번만 도는 벨만-포드
// 1) 743의 다익스트라를 그대로 얹으면 틀린다. 다익스트라는 "힙에서 꺼낸 순간 최단 확정"으로
//    노드를 한 번만 닫는데, 예제 1이 정확히 그 확정을 무너뜨린다 — 도시 2에 가장 싸게 닿는 경로는
//    0-1-2 = 200 이지만 그 경로는 이미 경유를 1번 썼고, 거기서 3으로 더 가면 경유 2회가 되어 실격.
//    답은 더 비싼 0-1-3 = 700 이다. "싸게 도착한 경로"가 "더 갈 수 있는 경로"가 아니다.
//    상태가 (도시)가 아니라 (도시, 사용한 경유 수)라서 방문 확정 구조 자체를 버려야 한다.
// 2) 경유 k번 이하 = 비행기를 최대 k+1번 타는 것 = 간선을 k+1개 이하 쓰는 것.
//    "간선을 r개 이하 써서 도달하는 최소 비용"을 r 을 올려 가며 갱신하면 되고, 그게 라운드를
//    k+1번만 도는 벨만-포드다. 힙도 방문 배열도 없다. 사실상 dp[라운드][도시] 테이블이고
//    아래 스냅샷 방식이 그 테이블의 행 하나만 굴리는(rolling) 최적화다.
// 3) 이 문제의 전부는 prev 스냅샷 한 줄이다. 제자리에서 dist 를 갱신하면 같은 라운드 안에서
//    방금 갱신된 값이 연쇄로 또 갱신된다 — 간선 순회가 [0,1,100] → [1,2,100] 이면 한 라운드에
//    0 → 1 → 2 가 다 퍼져 비행기를 2번 탄 경로가 라운드 1에 섞인다. 14497에서 큐 두 개로
//    점프 단위를 끊었던 것과 같은 이유로, 읽는 쪽(prev)과 쓰는 쪽(dist)을 갈라 둔다.
//    스냅샷을 빼면 예제 1이 400을 낸다 — 그건 제약을 무시했을 때의 '실제 최단경로 비용'이라
//    값만 보고는 버그를 의심할 수 없다. 오답이 다른 조건에서의 정답이면 잡기 어렵다.
// 4) 라운드 수 off-by-one: 경유 k번 = 간선 k+1개이므로 r <= k (k+1회)가 맞다. r < k 로 짜면
//    예제 3(k=0, 직항 500)이 라운드를 0번 돌아 -1 이 된다. k=0 예제가 이 실수를 잡아 준다.
// 5) INF 는 -1. prev[from] == -1 인 도시는 아직 못 간 곳이라 건너뛰고, 목적지가 끝까지 -1 이면
//    return dist[dst] 가 그대로 "경로 없음"의 답이 된다 → 간선 0개 입력도 별도 분기 없이 처리된다.
//    사이클이 있어도 라운드가 k+1로 막혀 있고 price >= 1 이라 무한 감소가 없다.
// 시간 O((k+1) * E) — 최악 약 50만 연산, 공간 O(n) (dist + prev 두 벌)

#include <vector>

using namespace std;

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k)
    {
        vector<int> dist(n, -1);          // -1 = 아직 못 감(무한대). 지역 vector라 리셋할 게 없다
        dist[src] = 0;                    // 출발지만 0

        for (int r = 0; r <= k; r++)      // 라운드 k+1번 = 비행기 최대 k+1번 = 경유 k번 이하
        {
            vector<int> prev = dist;      // 갱신 직전 스냅샷 — 한 라운드 안의 연쇄 갱신 차단

            for (auto& f : flights)       // f = {from, to, price}
            {
                if (prev[f[0]] == -1) continue;      // 아직 못 간 도시에서 출발하는 편은 무의미

                int cost = prev[f[0]] + f[2];        // 읽는 쪽은 prev, 쓰는 쪽은 dist

                if (dist[f[1]] == -1 || cost < dist[f[1]]) dist[f[1]] = cost;   // -1 가드가 INF 비교
            }
        }

        return dist[dst];                 // 끝까지 -1 이면 경로 없음 — 그대로 답이 된다
    }
};

정리

• 상태에 축이 하나 더 붙으면 방문 확정 구조를 버려야 한다. 상태가 (도시, 경유 수)인데 비용만으로 도시를 닫으면, 비싸지만 경유를 덜 쓴 경로가 지워진다. 예제 1이 그 반례로 설계돼 있다 — 도시 2를 200으로 확정하는 순간 정답 700이 사라진다. 1697 숨바꼭질에서 정리한 “방문 체크는 상태의 모든 축을 포함해야 한다”의 다른 얼굴이다.
• 제한 횟수는 라운드 수로 표현하는 게 제일 단순하다. 경유 k회 = 간선 k+1개 = 라운드 k+1번이고, 그러면 힙도 방문 배열도 필요 없어진다. r <= k인지 r < k인지는 k=0 예제 하나로 검증하고 넘어간다 — r < k면 라운드가 0번 돌아 직항 500이 -1이 된다.
• 읽는 쪽과 쓰는 쪽을 갈라 두는 prev = dist 한 줄이 라운드 제한을 지탱한다. 제자리 갱신은 간선 순회 순서에 따라 한 라운드 안에서 0 → 1 → 2를 연쇄로 퍼뜨려 경유 제한을 조용히 무너뜨린다. 14497에서 큐 두 개(q / temp)로 점프 단위를 끊은 것과 같은 발상이고, 문제 유형으로 보면 dp[라운드][도시]의 행 하나만 굴리는(rolling) 방식이다.
• 오답이 다른 조건에서의 정답이면 값만 보고는 못 잡는다. 스냅샷을 빼면 예제 1이 400을 내는데, 그건 경유 제한을 무시했을 때의 실제 최단경로 비용이다. 그래서 검증 케이스를 “정답 하나”로 두지 말고 k를 바꿔 답이 함께 바뀌는지로 잡아야 한다 — k=1에서 700, k=2에서 400이 둘 다 맞아야 경유 제한이 실제로 작동한다는 뜻이 된다.
• -1 인코딩이 판정 코드를 두 군데서 없앤다. prev[from] == -1이면 출발 자체가 무의미해 건너뛰고, 목적지가 끝까지 -1이면 return dist[dst]가 그대로 문제의 요구 출력과 일치한다. 간선 0개 입력이 별도 분기 없이 처리되는 것도 그 덕이다. 사이클은 라운드가 k+1로 막혀 있고 price ≥ 1이라 무한 감소가 없다.
• 상한 점검: n ≤ 100, E ≤ 4950, k < 100이라 최악 약 50만 연산이고, 라운드마다 벡터를 한 벌 복사하는 비용도 O(n·k)로 무시할 수 있다. n이 커지면 그 복사가 부담이 되므로 dp[2][n] 두 행을 번갈아 쓰는 방식으로 바꾼다.
• 검증: 예제 3개 + 간선 0개(-1) + 예제 1을 k=2로 완화(400) + k=0인데 직항 없음(-1) + 사이클 포함(3) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 상태가 (도시, 사용한 경유 수)라서 비용만으로 도시를 확정하는 다익스트라는 예제 1에서 무너진다(도시 2를 200으로 닫으면 경유 2회가 되어 실격, 정답은 더 비싼 700). 경유 k회 = 간선 k+1개이므로 라운드를 k+1번만 도는 벨만-포드로 풀고, 라운드마다 prev = dist 스냅샷을 떠서 그것만 보고 갱신해야 한 라운드 안의 연쇄 갱신이 막힌다. 스냅샷을 빼면 실제 최단경로 값인 400이 나와 오답이 정답처럼 보이므로, 검증은 k를 바꿔 답(700 ↔ 400)이 같이 바뀌는지로 한다.