1 분 소요

Cheapest Flights Within K Stops - LeetCode

문제 정리

  • n개의 도시
  • flights[i] = [fromi,toi,pricei]
  • src → dst까지 최대 k개의 정거장을 거치는 방법 중 가장 저렴한 가격을 구하라

풀이 1 : 다익스트라 알고리즘

  • 기본적으로 다익스트라 문제 + 최대 k개의 정거장을 거친다는 추가적인 조건
  • 다익스트라 알고리즘 특징
    • 이미 최단거리를 구한 정점에 대해서는 다시 우선순위 큐에 추가하지 않음 → 근데 이 경로가 하필이면 너무 많은 노드를 거쳤다면? 그래서 목적지까지 도달하기 위한 남은 step이 없다면? 영원히 도착지에 도달하지 못하게 된다.
    • 따라서 이 문제의 경우, 설령 최단 거리가 아니더라도 거쳐간 노드 수가 더 작다면 탐색 대상에 추가한다 (= 큐에 추가)
  • 시간 복잡도 : O(V^2logV)
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    # make graph
    graph = defaultdict(list)
    for u, v, price in flights:
        graph[u].append((v,price))

    # shortest distances array
    distances = [float("inf") for _ in range(n)]
    current_stops = [float("inf") for _ in range(n)]    # i 노드까지 거쳐간 최소 노드의 수
    distances[src], current_stops[src] = 0, 0

    # Data is (cost, stops, node)
    pq = [(0,0,src)]

    while pq:
        cost, stops, node = heapq.heappop(pq)
        # if destination is reached, return the cost to get there
        if node == dst:
            return cost

        # if there are no more steps left, continue
        if stops == k+1:
            continue

        # Examine and relax all neighboring edges if possible
        for v, w in graph[node]:
            # better cost?
            if cost+w < distances[v]:
                distances[v] = cost+w
                heapq.heappush(pq, (cost+w, stops+1, v))
                current_stops[v] = stops
            elif stops < current_stops[v]:   # 걍 애도 일단 고려를 해주겠다는 것임 (설령 최소 거리가 아니더라도)
                # Better steps?
                heapq.heappush(pq, (cost+w, stops+1, v))

    return -1 if distances[dst] == float("inf") else distances[dst]

풀이 2 : DFS + Memoization

  • 이 문제는 그래프 상에서의 DP 문제로도 해석할 수 있다.
  • dfs(node, stops) : 현재 노드, 남은 stop 개수
def __init__(self):
    self.adj_matrix = None
    self.memo = {}

def dfs(self, node, stops, dst):

    # No need to go any further if the destination is reached    
    if node == dst:
        return 0

    # Can't go any further if no stops left
    if stops < 0:
        return float("inf")

    # If the result of this state is already cached, return it
    if (node, stops) in self.memo:
        return self.memo[(node, stops)]

    # Recursive calls over all the neighbors
    ans = float("inf")
    for neighbor, w in graph[node]
        ans = min(ans, self.dfs(neighbor, stops-1, dst, n) + w)

    # Cache the result
    self.memo[(node, stops)] = ans        
    return ans

참고