Cheapest Flights Within K Stops
n개의 도시가 있으며, 각 도시는 0부터 n-1까지 번호가 매겨져 있고, 편도 항공편 목록이 주어집니다. flights[i] = [from, to, price]는 도시 from에서 도시 to로 가는 항공편이며 비용은 price입니다.
이동 중 최대 k번 경유하는 src에서 dst까지의 여행에 드는 최소 총 비용을 반환하세요. 즉, 항공편을 최대 k+1개 이용할 수 있습니다. 그러한 여행이 없다면 -1을 반환하세요.
함수
- ninteger
- 도시의 수
- flightsinteger-2d-array
- 각각 [from, to, price] 형식인 편도 항공편
- srcinteger
- 여행이 시작되는 도시
- dstinteger
- 여행이 끝나는 도시
- kinteger
- src와 dst 사이에 허용되는 최대 경유지 수
- 반환값integer
- 경유지가 최대 k개인 여행의 최저 가격 또는 -1
제약 조건
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]에서0 ≤ from, to < n이고from ≠ to입니다1 ≤ price ≤ 104- 두 항공편이
from과to를 모두 공유하는 경우는 없습니다. 0 ≤ src, dst < n이고src ≠ dst0 ≤ k < n
예제
- 입력
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- 출력
- 230
- 설명
- 경유지 한 곳으로 두 번의 비행이 가능합니다:
0 → 1 → 3의 비용은 50 + 180 = 230이고,0 → 2 → 3의 비용은 200 + 50 = 250입니다. 더 저렴한0 → 1 → 2 → 3은 경유지가 두 곳입니다.
- 입력
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- 출력
- 150
- 설명
- 경유지 두 곳이면 항공편 세 번을 이용할 수 있으므로, 이제
0 → 1 → 2 → 3이 허용되며 비용은 50 + 50 + 50 = 150입니다.
- 입력
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 0
- 출력
- -1
- 설명
- 중간 정차가 없으므로 0에서 3까지 한 번에 비행해야 하지만, 그런 항공편은 없습니다.
후속 질문
가장 저렴한 여행의 도시들과 그 가격을 어떻게 반환할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
전체적으로 가장 저렴한 여정에는 경유지가 너무 많을 수 있으므로, 단순히 최단 경로만으로는 충분하지 않습니다. 가격은 이용한 항공편 수와 함께 고려해야만 유용합니다.
cost[c]를 최대r회의 항공편으로 도시c에 도달하는 최저 비용이라고 하자. 모든 항공편을 한 번씩 살펴보면 최대r+1회의 항공편으로 도달하는 최저 비용을 구할 수 있다. 이런 과정을k+1번 반복해야 한다.각 반복에서 이전 반복의 가격을 읽고 복사본에 씁니다. 제자리에서 업데이트하면 같은 반복에서 설정된 가격을 바탕으로 항공편이 추가될 수 있으며, 한 번의 반복에 항공편 두 개가 몰래 들어갑니다.
풀이
이는 항공편 수에 제한이 있는 최단 경로 문제입니다. 도시만을 대상으로 다익스트라 알고리즘을 적용하면 실패합니다. 어떤 도시에 도착하는 가장 저렴한 경로가 남은 여정에 필요한 경유 횟수를 모두 써버릴 수 있기 때문입니다. 벨만-포드 알고리즘은 이 제한에 적합합니다. r번째 라운드에서는 항공편을 최대 r번 이용했을 때의 최저 요금을 찾으므로, k+1번 라운드를 실행합니다.
최대 k+1개의 항공편으로 모든 경로를 시도하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
src에서 시작하는 모든 경로를 (도시, 가격, 이용한 항공편 수)로 이루어진 스택을 사용해 탐색합니다. dst에 도달한 경로는 가격을 기록하고 탐색을 끝냅니다. 모든 가격이 양수이기 때문입니다. 항공편을 k+1개 이용한 경로는 버리고, 그 외의 경로는 해당 도시에서 출발하는 모든 항공편을 이용해 확장합니다. 허용되는 모든 여정이 만들어지므로, 기록된 가격 중 최솟값이 정답입니다.
도시에서 출발하는 항공편이 d개라면 경로 수는 d의 k+1제곱만큼 증가합니다. 도시마다 항공편이 4개이고 k = 29라면, 경로 수는 4^30 ≈ 1.2 × 10^18입니다.
알고리즘
- 항공편을 출발 도시별로 그룹화합니다.
(src, 0, 0)을 푸시합니다: 도시, 지금까지의 가격, 이용한 항공편 수입니다.- 경로를 팝합니다. 해당 도시가
dst라면, 지금까지의 최저 가격인 경우 그 가격을 기록합니다. - 그렇지 않고 이용한 항공편 수가
k+1보다 적다면, 해당 도시에서 출발하는 각 항공편마다 한 구간 더 긴 경로를 푸시합니다. - 스택이 비면 최저 가격을 반환하고,
dst에 도달한 경로가 없다면 -1을 반환합니다.
def findCheapestPrice(n, flights, src, dst, k):
out = [[] for _ in range(n)]
for a, b, price in flights:
out[a].append((b, price))
best = -1
# Each entry is a route in progress: (city, price so far, flights taken).
stack = [(src, 0, 0)]
while stack:
city, cost, used = stack.pop()
if city == dst:
if best == -1 or cost < best:
best = cost
continue
# k stops allow at most k+1 flights.
if used == k + 1:
continue
for nxt, price in out[city]:
stack.append((nxt, cost + price, used + 1))
return bestk+1회 반복으로 제한된 Bellman-Ford
핵심 아이디어
cost[c]를 최대 r번의 항공편으로 도시 c에 도달하는 최저 가격이라고 하자. r = 0일 때는 src만 도달 가능하며, 가격은 0이다. 최대 r번의 항공편으로 a에 간 다음 항공편 a → b를 이용하면 최대 r+1번의 항공편으로 b에 갈 수 있으므로, 각 라운드에서 모든 항공편에 대해 b에 cost[a] + price를 제시한다. k+1번의 라운드가 끝나면 cost[dst]가 정답이다.
각 라운드는 이전 라운드의 가격을 읽고 복사본에 기록하므로, 한 라운드에서 설정된 가격은 같은 라운드의 다른 항공편에 이어서 사용할 수 없다. k = 1인 첫 번째 예시에서 도시 2의 가격은 2라운드에 100으로 떨어지지만, 도시 3까지 150에 가는 항공편을 이용할 라운드는 남아 있지 않다.
각 라운드에서 모든 항공편을 한 번씩 읽는다. 항공편이 E개일 때 시간 복잡도는 O(k · E)이고, 두 배열을 위한 공간 복잡도는 O(n)이다.
알고리즘
cost[src] = 0으로 설정하고, 나머지 모든cost는 무한대로 설정합니다.k+1번 반복합니다:cost를next에 복사합니다.cost[a]가 유한한 모든 항공편[a, b, price]에 대해,cost[a] + price < next[b]이면next[b] = cost[a] + price로 설정합니다.cost를next로 바꾸고, 변경된 내용이 없으면 일찍 종료합니다.cost[dst]를 반환하거나, 여전히 무한대이면 -1을 반환합니다.
def findCheapestPrice(n, flights, src, dst, k):
INF = float("inf")
# cost[c]: the cheapest price to reach city c with the flights allowed so far.
cost = [INF] * n
cost[src] = 0
# Each round allows one more flight; k stops means k+1 flights.
for _ in range(k + 1):
# Read last round's prices and write into a copy,
# so one round can never chain two flights.
nxt = cost[:]
changed = False
for a, b, price in flights:
if cost[a] != INF and cost[a] + price < nxt[b]:
nxt[b] = cost[a] + price
changed = True
cost = nxt
if not changed:
break
return -1 if cost[dst] == INF else cost[dst]
함정과 경계 사례
- 경유지를 항공편 수로 세기.
k개의 경유지는k+1개의 항공편과k+1개의 라운드를 의미합니다. - 제자리에서 갱신하기. 각각 비용이 1인
0 → 1,1 → 2,2 → 3을 이 순서대로 처리하고, 비용이 500인0 → 3과k = 0이 주어지면, 한 라운드에서 항공편 세 개가 연쇄적으로 처리되어 500이 아니라 3을 반환합니다. - 도시를 대상으로 일반적인 Dijkstra 알고리즘 실행하기. 각각 비용이 1인
0 → 1과1 → 2, 비용이 40인0 → 2, 비용이 1인2 → 3, 그리고k = 1이 주어지면, 항공편 두 개를 거쳐 비용 2로 도시 2를 확정하므로 비용 41인0 → 2 → 3경로를 놓칩니다. - 아직 도달하지 않은 도시에서 출발하기. 무한대가 가장 큰 int일 때
cost[a] + price는 32비트에서 음수로 오버플로됩니다. 먼저cost[a]가 유한한지 확인하세요.
자주 묻는 질문3
K번 이하 경유로 가장 저렴한 항공편의 시간 복잡도는 무엇인가요?
k+1회로 제한한 Bellman-Ford는 E개의 항공편에 대해 O(k · E) 시간이 걸리고, 두 개의 가격 배열에 O(n)의 추가 공간이 필요합니다. 아무것도 바뀌지 않는 라운드에서는 다음 라운드에도 같은 가격이 전달되므로 일찍 종료할 수 있습니다.
왜 다익스트라 알고리즘은 K회 이하 경유하는 최저가 항공편 문제에서 작동하지 않을까요?
Dijkstra는 도시마다 가장 좋은 가격 하나를 유지하며, 확정된 도시는 다시 방문하지 않습니다. 여기서는 도시까지 가는 데 항공편을 더 적게 이용했다면 더 비싼 경로가 유용할 수 있습니다. Dijkstra는 다시 상태 (도시, 이용한 항공편 수)를 기반으로 작동하며, 이 경우 상태 수가 k+1배가 됩니다.
K번 이하 경유로 가장 저렴한 항공편을 BFS로 찾는 문제를 풀 수 있나요?
네. 레벨 r에는 정확히 r번의 항공편을 이용해 도달한 도시와 그 요금이 들어갑니다. 새 요금이 해당 도시에서 확인한 최저 요금보다 낮을 때만 그 도시를 다음 레벨에 추가하고, k+1개 레벨이 지나면 멈춥니다. Bellman-Ford와 같은 답을 구하지만, 요금이 변경된 도시에서 출발하는 항공편만 따라갑니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def findCheapestPrice(n, flights, src, dst, k):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
n = 4 flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]] src = 0 dst = 3 k = 1
예상 출력
230