[LeetCode] 787. Cheapest Flights Within K Stops

📃 문제 설명

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

• 유향 그래프와 경로 시작점, 끝점이 주어져 있을 때, k개 이하의 node를 거쳐 끝점에 도착할 수 있는 최소 금액을 출력하는 문제이다. 불가능할 경우 -1을 출력한다.

🔎 문제 접근

• 처음에는 Dijkstra 알고리즘 을 생각했으나, 해당 알고리즘은 최소 경로를 찾는데 유용하기에 k개 이하의 node를 거친다는 constraint가 존재할 경우 사용하기에 적절하지 않다는 생각이 들었다.
• 다음으로 생각한 알고리즘은 Bellman-Ford 알고리즘 이다. 해당 알고리즘은 vertex의 수 - 1 번 모든 vertex에 대해 연결된 타 vertex를 거쳐 오는 게 더 짧은지 비교하는 알고리즘으로 그래프 내에 음수 distance가 존재하더라도 풀 수 있다.
  • 해당 알고리즘을 응용해, k번 동안 모든 vertex에 대한 update 과정을 진행해 답을 출력하는 알고리즘을 작성했다.

✨ 문제 풀이

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = [[] for _ in range(n)]
        for f, t, p in flights:
            graph[f].append((t, p))
        
        k += 1
        visited_price = [[10 ** 6] * n for _ in range(k+1)]
        visited_price[0][src] = 0
        
        for idx in range(1, k+1):
            for now_node in range(n):
                if visited_price[idx-1][now_node] < 10**6:
                    for next_node, price in graph[now_node]:
                        visited_price[idx][next_node] = min(visited_price[idx][next_node], visited_price[idx-1][now_node] + price) 
                        
        min_price = min(visited_price[idx][dst] for idx in range(k+1))
        return -1 if min_price == 10**6 else min_price

• 빠르지는 않지만 memory usage에서 이득을 본 알고리즘을 작성할 수 있었다.
• 다른 사람들의 코드를 살펴보다 Dijkstra 알고리즘을 사용한 코드를 확인할 수 있었다. [링크] 해당 코드는 heap을 사용했는데, 좋은 알고리즘인지는 잘 모르겠다.