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

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

4. 배운 점

• 굉장히 까다로운 문제였다.
• 최근 테스트케이스가 추가됨에 따라, 책에 있던 풀이는 통과되지 못하였고 구글링 및 질문게시판을 참고하여 답을 보고 재구현 해 보았다.

5. 총평

다익스트라 알고리즘 익히기