Leetcode-787.Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

주어진 정보를 활용해 src에서 dst까지 이동할 때 최대 k stop 횟수 내에서 가장 저렴한 비용을 반환하는 문제이다.

0 -> 1 -> 2 -> 3이 400으로 가장 저렴한 비용이지만 2 stop으로 문제 조건 k=1을 초과한다. 때문에 0 -> 1 -> 2 루트가 1 stop으로 정답 700을 반환하게 되는 것이다.

해당 문제는 deque를 이용해 k stop 이내로 움직이게 되는 조건만 확인하면 쉽게 풀린다.

• 정답 코드

from collections import deque as dq

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        
        visit = [0 for _ in range(n)] #방문 체크
        
        flights_dic = {} #모든 비행 정보를 딕셔너리에 저장
        for tmp_src, tmp_dst, tmp_price in flights:
            if tmp_src in flights_dic: #딕셔너리에 현재 출발지 정보가 있다면
                flights_dic[tmp_src].append([tmp_dst, tmp_price])
            else: 
                flights_dic[tmp_src] = [[tmp_dst, tmp_price]]
                
        #print(flights_dic)
        
        q = dq([])
        now_price = 0 #현재까지 비행 비용
        move_count = 0 #움직임 카운트
        q.append([src, now_price, move_count])
        visit[src] = 1
        
        while q:
            popQ = q.popleft()
            now_src = popQ[0]
            now_price = popQ[1]
            now_move_count = popQ[2]
            
            if now_move_count > k: #현재까지의 움직임이 k를 넘는다면 현재 pop 생략
                continue
            
            if now_src in flights_dic: #현재 출발지에서의 비행 정보가 딕셔너리에 있다면
                for next_info in flights_dic[now_src]:
                    #print(popQ, next_info)
                    next_src = next_info[0]
                    next_price = next_info[1]
                    
                    #다음 도착지가 미방문 혹은 더 저렴한 가격이라면
                    if visit[next_src] == 0 or visit[next_src] > now_price + next_price:
                        q.append([next_src, now_price + next_price, now_move_count + 1])
                        visit[next_src] = now_price + next_price
        
        if visit[dst] == 0:
            return -1
        else:
            return visit[dst]