[LeetCode] 787. Cheapest Flights Within K Stops

n개 도시, 항공편 [from, to, price] 목록이 주어진다. src에서 dst까지 최대 k번 경유로 갈 수 있는 최저가를 구하라. 없으면 -1.

1. 첫 시도: DFS 백트래킹 → 시간 초과

function findCheapestPrice(n, flights, src, dst, k) {
    const graph = new Map()
    for (const [from, to, price] of flights) {
        graph.set(from, [...(graph.get(from) ?? []), { to, price }])
    }
    let cheapest = Infinity
    const visited = new Set()
    function backTrack(curr, stop, total) {
        if (curr === dst) { cheapest = Math.min(cheapest, total); return }
        if (stop > k || total >= cheapest) return
        for (const { to, price } of graph.get(curr) ?? []) {
            if (visited.has(to)) continue
            visited.add(to)
            backTrack(to, stop + 1, total + price)
            visited.delete(to)
        }
    }
    backTrack(src, 0, 0)
    return cheapest === Infinity ? -1 : cheapest
}

visited로 중복을 막았는데 왜 느릴까?

• visited는 한 경로 안의 사이클만 막는다. 같은 도시에 다른 경로로 도달하는 건 매번 다시 탐색한다.
• 결국 가능한 경로를 전부 나열하는 셈이라 경로 수가 지수적으로 늘어난다.
• total >= cheapest 가지치기는 최적해를 늦게 찾으면 거의 효과가 없다.

2. 발상 전환: "경로"가 아니라 "간선 개수"로 접근

경유 k번 = 항공편 최대 k+1개.

그러니 질문을 이렇게 바꾼다.

"항공편 1개로 각 도시까지 최저가는?" → "2개로는?" → ... → "k+1개로는?"

이걸 k+1번 반복하면 끝난다. 이게 벨만-포드(Bellman-Ford) 알고리즘이다.

3. 풀이

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    let dist = new Array(n).fill(Infinity)
    dist[src] = 0
    for (let i = 0; i <= k; i++) {
        const next = [...dist]
        for (const [from, to, price] of flights) {
            if (dist[from] + price < next[to]) next[to] = dist[from] + price
        }
        dist = next
    }
    return dist[dst] === Infinity ? -1 : dist[dst]
}

• dist[i] = 지금까지 허용된 간선 수로 도시 i까지 가는 최저가
• 라운드마다 모든 항공편을 한 번씩 훑으며 dist를 갱신
• k+1 라운드 후 dist[dst]가 답
• 시간복잡도 O(k · E), 경로 수와 무관하다

4. 왜 next 복사본에 갱신하나?

dist를 제자리에서 바로 갱신하면 같은 라운드 안에서 방금 갱신된 값이 다음 간선에 쓰인다. 한 라운드에 간선이 여러 개 늘어나 k 제한이 깨진다.

Example 1 (k = 1, 정답 700)로 확인해보자.

flights = [0,1,100], [1,2,100], [2,0,100], [1,3,600], [2,3,200]

제자리 갱신 (틀림)

라운드 0: dist = [0, Inf, Inf, Inf]
  [0,1,100] → dist[1] = 100
  [1,2,100] → dist[2] = 200   ← 방금 바뀐 dist[1]을 바로 씀 (간선 2개째)
  [1,3,600] → dist[3] = 700
  [2,3,200] → dist[3] = 400   ← 0→1→2→3, 경유 2번. k 초과!
답: 400 (오답)

복사본 갱신 (맞음)

라운드 0: dist = [0, Inf, Inf, Inf]
  [0,1,100] → next[1] = 100
  나머지는 dist[from]이 Inf라 스킵
  dist = [0, 100, Inf, Inf]        (간선 1개 이내)

라운드 1:
  [1,2,100] → next[2] = 200
  [1,3,600] → next[3] = 700
  [2,3,200] → dist[2]는 아직 Inf → 스킵
  dist = [0, 100, 200, 700]        (간선 2개 이내)
답: 700

핵심은 갱신할 때 읽는 값이 dist[from], 즉 이전 라운드의 스냅샷이라는 것. 그래서 라운드마다 정확히 간선 하나씩만 늘어난다.

정리

	DFS 백트래킹	벨만-포드
탐색 단위	경로	간선 개수(라운드)
복잡도	경로 수에 비례 (지수)	O(k · E)
k 제한	재귀 깊이로	라운드 수로

"몇 번 경유" 같은 횟수 제한이 붙은 최단 경로는 다익스트라보다 벨만-포드가 자연스럽다. 라운드 수 = 허용 간선 수이기 때문이다.