[알고리즘][최단 거리] - 2.k 경유지 내 가장 저렴한 항공권

 

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

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

시작점에서 도착점까지의 가장 저렴한 가격을 계산하되. k개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다.

---

[다익스트라 응용버전]

import collections
import heapq


class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):
        graph = collections.defaultdict(list)
        
        for u,v,w in flights:
            graph[u].append((v,w))
        
        q = [(0,src, k)]
        
        while q:
            price, node, k = heapq.heappop(q)
            
            if node == dst:
                return price
            if k >= 0:
                for v,w in graph[node]:
                    alt = price+w
                    heapq.heappush(q,(alt,v,k-1))
        return -1

• k개의 경유지 이내의 도착이라는 조건이 있음을 유의하고 풀어야 한다.