[LeetCode] 787. Cheapest Flights Within K Stops [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Cheapest Flights Within K Stops - LeetCode>

1. 문제 (K경유지 내 가장 저렴한 항공권)

시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라.

경로가 존재하지 않을 경우 -1을 리턴한다.

2. 풀이

다익스트라 알고리즘을 이용한 풀이

collections.defaultdict(lambda : float('inf')) : 딕셔너리에 int의 최대값을 기본값으로 설정

3. 코드

import collections

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        if src == dst: return 0

        graph = collections.defaultdict(list)

        for f, t, p in flights:
            graph[f].append((t, p))

        visited = collections.defaultdict(lambda : float('inf'))
        dq = collections.deque()
        dq.append((src, 0, k))

        while dq:
            c, p, k = dq.popleft()
            if c == dst or k == -1: continue
            for nc, np in graph[c]:
                if p + np >= visited[nc]:
                    continue
                else:
                    visited[nc] = p + np
                    dq.append((nc, p + np, k - 1))

        return visited[dst] if visited[dst] < float('inf') else -1

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	1000 ms	15.2 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋