LeetCode 787. Cheapest Flights Within K Stops

파이썬 알고리즘 인터뷰 문제 41번(리트코드 787번) Cheapest Flights Within K Stops
https://leetcode.com/problems/cheapest-flights-within-k-stops/

나의 풀이(미해결, Time Limit Exceeded)

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for from_, to, price in flights:
            graph[from_].append((to, price))
        prices = collections.defaultdict(list)

        Q = [(0, 0, src)] # price, stops, city

        while Q:
            price, stops, city = heapq.heappop(Q)
            #print(price, stops, city, prices)
            #print(Q)
            if stops <= k + 1:
                prices[city].append([price, stops])
                for nei, delta_price in graph[city]:
                    heapq.heappush(Q, (price + delta_price, stops + 1, nei))
        #print(prices)
        if dst in prices:
            return min(price[0] for price in prices[dst] if price[1] <= k + 1)
        return -1

다른 풀이

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        graph = collections.defaultdict(list)
        weight = [(float('inf'), K)] * n
        # 그래프 인접 리스트 구성
        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
                    if alt < weight[v][0] or k-1 >= weight[v][1]:
                        weight[v] = (alt, k-1)
                        heapq.heappush(Q, (alt, v, k - 1))
        return -1

• 내 풀이는 다익스트라 알고리즘을 변형한 것이지만, 경유지 수가 초과한 경우만 제외하고 모두 탐색하는 dfs이다.
• 하지만 이미 탐색한 것 보다 불리한 경로를 탐색할 필요가 없다.
• 보다 유리하려면 비용이 저렴하거나, 경유지 수가 적어야 한다.
• 이 경우만 탐색에 추가하는 것으로 바꾸면 풀린다.
• 당연한 아이디어인데 아직 익숙하지 않은 유형이라 그런지 당연한 생각을 코드에 반영하지 못했다.