[leetcode] cheapest flights within k stops

cheapest flights within k stops

• flights 로 연결되어 있는 n 개의 도시
• flight 는 (from, to , price) 로 구성 - 출발, 도착, 가격
• src(출발점), dst(도착점), k(경유 제한개수)가 주어진다
• 출발점에서 도착점 까지의 k 번의 경유 이내로 도착하는 최소 비용 리턴
• 두 도시간 중복된 비행은 없음
• k= 0 이면 직항 만을 의미
• 1 <= n <= 100 , 도시 개수
• 0 <=s src, dst, k < n

Solution1

• 다익스트라 최단경로 알고리즘
• src=A, dst=C 일때
  • (경로1) A-A1-B, 비용 9, 노드 3개
  • (경로2) A-A2-A3-A4-B, 비용 7, 노드 5개
  • (경로3) B-B1-C, 비용 3, 노드 3개
  • A - C의 최단경로 : 7 + 3 = 10
  • A - C의 최단경로 (노드 수 5개 제한 존재할때) 9 + 3 = 12
• 비용이 줄지만 노드가 더 많이 사용된 경로 + 비용은 증가하지만 노드가 더 적게 사용된 경로 모두 기록필요
• prices 를 2차원으로 기록 prices[n][w] # n번의 경유로 w 노드로 도착하는 최단 경로
• 경유 제한(k)가 초과되는 경우는 skip
• flight 중에서 도착점이 src 인경우, 출발점이 dst 인 경우 고려 안해도 결과 동일

Code1

from collections import defaultdict
import heapq

class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):

        # prices[d][n] : d 번의 경유로 n노드에 도착하는 최소 값
        prices = [defaultdict(int) for _ in range(k+1)]
        graph = defaultdict(list)

        # ( price, stops, dst)
        q = []

        for v, w, cost in flights:
            if v == src : heapq.heappush(q,(cost,0,w))
            elif w == src or v == dst : continue  
            else : graph[v].append((cost, w))


        while q:
            price, stops, v = heapq.heappop(q)
            if v == dst : return price
            if v in prices[stops]: continue

            prices[stops][v] = price
            for cost, w in graph[v]:
                if stops+1 > k : continue    
                if stops+1 == k and w != dst : continue                            
                heapq.heappush(q, (cost + price, stops + 1, w))

        return -1

Solution2

• prices[i][j] # i 노드에 j번의 stops로 도착하는 최단 경로
• price = prices[i][j] 일때 prices[i][:j] 중 price보다 더 작거나 같은 경우(비용줄지 않고, stops는 증가)있으면 고려하지 않음

Code2

from collections import defaultdict
import heapq


class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):

        INF=int(1e9)

        # prices[i][j] : i노드에  j번의 경유를 거쳐서 도착하는 최소 비용
        prices = [[INF]*(k+1) for _ in range(n)]
        graph = defaultdict(list)

        # ( price, stops, dst)
        q = []

        for v, w, cost in flights:
            if v == src : heapq.heappush(q,(cost,0,w))
            elif w == src or v == dst : continue
            else : graph[v].append((cost, w))

        while q:
            price, stops, v = heapq.heappop(q)
            if v == dst :
                return price
            if prices[v][stops] <= price: continue
            prices[v][stops] = price
            if stops >0 and min( prices[v][ :stops]) <= price : continue
            
            for cost, w in graph[v]:
                if stops+1 > k : continue
                if stops+1 == k and w != dst : continue
                heapq.heappush(q, (cost + price, stops + 1, w))
        return -1

Solution3

• k=0 일때 예외처리

from collections import defaultdict
import heapq


class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):

        INF=int(1e9)

        # prices[n][d] : n노드에  d번의 경유를 거쳐서 도착하는 최소 비용
        prices = [[INF]*(k) for _ in range(n)]
        graph = defaultdict(list)        
        q = [] # ( price, stops, dst)

        for v, w, cost in flights:
            if v == src : heapq.heappush(q,(cost,0,w))
            elif w == src or v == dst : continue
            else : graph[v].append((cost, w))

        if k == 0 : 
            res = [ x for x,y,z in q if z == dst ] 
            return -1 if len(res) == 0 else res[0]

        while q:
            price, stops, v = heapq.heappop(q)
            if v == dst : return price

            if prices[v][stops] <= price: continue
            prices[v][stops] = price

            if stops > 0 and min( prices[v][:stops] ) <= price : continue                        

            for cost, w in graph[v]:
                if stops+1 > k : continue
                if stops+1 == k and w != dst : continue
                heapq.heappush(q, (cost + price, stops + 1, w))
        return -1