[LeetCode/Python] 787. Cheapest Flights Within K Stops

시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, k개의 경유지 이내에 도착하는 가격을 리턴하라.

 

경로가 존재하지 않을 경우 -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.

 

 

 

 

1. 책 내의 풀이

 

 

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        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

 

 

해설

 

주어진 경로를 graph에 싹 넣어둔다.

 

src에서 시작하여 비용이 적게 드는 순서대로 진행될텐데

 

여기서 중요한 점은 경유지를 k 이하로 거쳐야 한다는 것이다.

 

따라서 보통 (price, node)를 Q에 push 해줬지만

 

위와 같이 거쳐간 경유지 또한 같이 넣어준다.

 

최소 힙으로 꺼내오는 이유는

 

price가 최소인 순서대로 반복문을 통과시키도록 하다 보면

 

도착지가 포함된 price가 나타났을 때 바로 price를 리턴하면 되기 때문이다.

 

그러려고 최소 힙으로 받는 거다!

 

 

 

 

2. 어떤 외국인의 코드

 

 

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        #make an adjaceny matrix
        #this will follow modified dijkatra's algo
        graph=[[] for i in range(n)]
        for u,v,w in flights:
            graph[u].append((v,w))
        #initialize infinite values for all nodes
        output=[float('inf') for i in range(n)]
        #start with source and hence mark it's weight as 0
        output[src]=0
        #construct graph
        Q=deque()
        #append the src , -1 as strp and 0 as cost to graph
        Q.append((src,-1,0))
        #now iterate over graph
        while Q:
            u,step,cost=Q.popleft()
            #if i have exhausted all steps
            if step>=k:
                continue
            for v,w in graph[u]:
                #classic dijkatr's algo
                if cost+w<output[v]:
                    output[v]=cost+w
                    Q.append((v,step+1,cost+w))
        if output[dst]==float('inf'):
            return -1
        return output[dst]

 

해설

 

내가 어떤 외국인의 코드를 가져온 이유는

 

1번 코드를 실행시켰을 때 "시간 초과"가 떴다...

 

그래서 외국 형님의 코드를 분석한 결과

 

1. defaultdict를 사용하지 않고 list로 graph를 생성함.

 

2. heapq를 쓰는 것보다 deque를 사용하여 막일 뛰는 것이 이 문제에선 더 빠르다(?)

 

정도로 생각된다.

 

시간 분석도 공부를 더 하면 왜 이게 더 빠른지 알 수 있겠지만 일단 내 뇌로는 이런 판단을 내렸다.

 

(사실 1번 코드가 더 효율적인 거 같은데.. defaultdict 쓰는 거 말고는...)

 

혹시 이유를 아시는 분은 댓글을 남겨주세요!