항해99, 5주차 K 경유지 내 가장 저렴한 항공권

Jang Seok Woo·2022년 2월 13일

다익스트라 최단경로

알고리즘

목록 보기

60/74

Today I learned
2022/02/07

회고록

2/07

항해 99, 알고리즘 4주차(항해 5주차)

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

최단경로

1. 이론

이론 정리 포스팅 글(내 벨로그)

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

2. 문제

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1:
링크텍스트

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

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

3. MySol

Dijkstra Algorithm

from collections import defaultdict
import heapq
from typing import List

INF = float('inf')


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adj = defaultdict(dict)
        for f, t, p in flights:
            adj[f][t] = p
        print(adj)
        stop = [INF] * n
        heap = [(0, 0, src)]

        while heap:
            current_price, current_stop, current_node = heapq.heappop(heap)

            if current_node == dst:
                return current_price
            if current_stop == k + 1 or current_stop >= stop[current_node]:
                continue

            stop[current_node] = current_stop

            for c, p in adj[current_node].items():
                heapq.heappush(heap, (current_price + p, current_stop + 1, c))

        return -1