[그래프] K 경유지 내 가장 저렴한 항공권

787 | Cheapest Flights Within K Stops 
https://leetcode.com/problems/cheapest-flights-within-k-stops/

 

 

 

작성 코드 (30분 제한)

 

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

        Q = [(0, src, k)]
        dist = collections.defaultdict(int)
        answers = []
        while Q:
            price, node, left = heapq.heappop(Q)
            if left == 0:
                print(graph[node], graph[node][0])
                if graph[node] and graph[node][0] == dst:
                    answers.append(graph[node][1])
                    break
            if node == dst and left == 0:
                answer = price
            if node not in dist:
                dist[node] = price
                for t, p in graph[node]:
                    alt = price + p
                    heapq.heappush(Q, (alt, t, left - 1))

        return answers

 

• left 가 0 이면 방문할 수 있는 기회가 끝, heapq 에 더이상 추가하지 않고 있는 것들 중에 조건을 만족하는 것을 뽑으려고 했음
• graph[node]가 있으면서 graph[node][0]이 목적지인 dst 와 같다면 answers에 append
• answers 배열을 생성한 이유는 해당 노드를 방문할 경로가 많을 경우 대비해서 return 할 때 min(answers)하려고 했음

 

 

이상 코드

 

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

 

• 문제를 잘못 이해한 부분 - K 경유지 이내 / 무조건 K개를 돌아야 하는 것이 아니였음
• 우선순위 큐 이기 때문에 만약 node == dst 가 같다면 현재 돌고 있는 price 값이 제일 작은 것, 바로 return
• k가 1이 아닌 0보다 크거나 같을 때만 도는 이유는 남은 경유지이기 때문에 k 가 0이어도 한 곳은 들릴 수 있음
• 책에 있는 코드라 가져왔는데 시간 초과 / 참고 코드 추가할 예정

 

 

학습

 

• 남은 경유지를 계산할 때 큐의 길이나 dist 의 길이로 len을 계산하려고 했는데 틀린 사고 방식이었음 / 남은 경유지의 개수인 K를 추가해줬으면 수월했던 문제
• 우선순위 큐이기 때문에 현재 돌고 있는 node가 dst와 같다면 price의 가격은 제일 저렴한 것임 / 큐의 특징을 잘 활용