[다익스트라 알고리즘]LeetCode 787.k정거장 내 가장 저렴한 항공권 | Python

LeetCode - The World's Leading Online Programming Learning Platform

1. 문제

입력값

n = 노드의 수

flights[i] = [[출발노드, 도착노드, 비용],...] (연결정보)

src = 출발지

dst = 도착지

k = 최대 경유 수

 

최대 K번의 경유를 통해 주어진 출발지에서 도착지까지의 최소 비용을 찾는 문제.

하지만, 비용이 더 비싸도 경유 수가 적은 노선을 선택한다.

 

제약조건

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 104
• 두 도시 간에는 여러 항공편이 운행되지 않습니다.
• 0 <= src, dst, k < n
• src != dst

 

2. 풀이

flights 리스트를 입력받아, graph 딕셔너리에 담아줬다.

파이썬의 '딕셔너리'는 java의 'HashMap'과 비슷하다.

 

1) 첫 번째에서는 시간초과 이슈로 틀렸음.

틀린 이유: 동일 노드를 여러번 방문 했고 , 최소비용과 경유 수를 추적하지 않았다.

import heapq
import json

# Time Limit Exceeded
# 더 최적경로를 찾는 조건을 추가해줘야할듯

def findCeapestPrice(n,flights,src,dst,K) -> int:
    #flights를 입력받아 [[출발지(u), 도착지(v), 비용(w)]]을 저장할 graph 딕셔너리를 만들어준다.
    #파이썬에서 딕셔너리는 java의 hashMap과 비슷하다.(key와 value로 저장)
    graph = {i:[] for i in range(n)}

    #flights 리스트를 순회한다.
    #graph딕셔너리의 u키에 해당하는 리스트에 튜플(v,w)을 추가.
    for u,v,w in flights:
        graph[u].append((v,w))

    #(비용,출발지 노드,남은 경유지 수)
    queue = [(0,src,K+1)]

    #큐가 빌 때까지 반복
    while queue:
        price, node, stop = heapq.heappop(queue)
        #현재 노드와 목적지 노드가 같다면 비용을 리턴한다.
        if node == dst:
            return price
        #남은 경유지 수가 0보다 크면(더 경유해야하면)
        if stop > 0:
            # graph딕셔너리의 node에서 출발하는 모든 항공편을 순회한다.
            for v, w in graph[node]:
                heapq.heappush(queue,(price + w, v, stop-1))
    #목적지 도달 못한 경우, -1 반환
    return -1

#입력 받는 부분
n = int(input())
flights = json.loads(input())
src = int(input())
dst = int(input())
K = int(input())

print(findCeapestPrice(n, flights, src, dst, K))

 

 

2) 두 번째에서는 각 노드당 최소 비용만 찾았기때문에 틀렸다.

import heapq

def findCheapestPrice(n, flights, src, dst, K):
    # flights를 입력받아 [[출발지(u), 도착지(v), 비용(w)]]을 저장할 graph 딕셔너리 생성
    graph = {i: [] for i in range(n)}
    for u, v, w in flights:
        graph[u].append((v, w))

    # 각 노드에 도달하기 위한 최소 비용을 저장할 딕셔너리
    min_cost_to_reach = {i: float('inf') for i in range(n)}
    min_cost_to_reach[src] = 0

    # (비용, 현재 노드, 남은 경유지 수) 튜플을 저장할 우선순위 큐
    queue = [(0, src, K + 1)]

    while queue:
        price, node, stops = heapq.heappop(queue)

        # 목적지에 도달하면 비용 반환
        if node == dst:
            return price

        # 남은 경유 횟수 확인
        if stops > 0:
            for v, w in graph[node]:
                next_price = price + w
                # 현재 경로가 이 노드에 도달하기 위한 기존 최소 비용보다 저렴하면 큐에 추가
                if next_price < min_cost_to_reach[v]:
                    min_cost_to_reach[v] = next_price
                    heapq.heappush(queue, (next_price, v, stops - 1))

    # 목적지에 도달할 수 없는 경우
    return -1

# 테스트 데이터
n =5
flights =[[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
src =0
dst =2
k = 2

 

첫 번째에 비해 개선된 부분

- 최소 비용을 저장할 딕셔너리를 추가함.

- 비용 비교하는 if문을 추가하고 더 저렴한 비용을 큐에 추가함.

 

3) 최종적으로 최소비용과 경유 횟수를 모두 고려하여 맞았다.

import heapq
import json

# Time Limit Exceeded
# 더 최적경로를 찾는 조건을 추가해줘야할듯
# 현재 문제점 : 동일 노드를 중복방문함.
# 개선점 : 동일 노드를 중복방문하지 않는다. 이미 탐색조건을 만족했다면 탐색을 중단한다.
# 개선한 부분
# 1. 최소비용 저장 딕셔너리 만들음 --> 테스트케이스 통과못함
# 2. 경유 횟수 추적(더 비싼 경로여도 더 적은 경유를 선택)

def findCeapestPrice(n,flights,src,dst,K):
    #flights를 입력받아 [[출발지(u), 도착지(v), 비용(w)]]을 저장할 graph 딕셔너리를 만들어준다.
    #파이썬에서 딕셔너리는 java의 hashMap과 비슷하다.(key와 value로 저장)
    graph = {i:[] for i in range(n)}

    #flights 리스트를 순회한다.
    #graph딕셔너리의 u키에 해당하는 리스트에 튜플(v,w)을 추가.
    for u,v,w in flights:
        graph[u].append((v,w))

    #각 노드에 도달하기 위한 최소 비용과 경유횟수를 저장하는 딕셔너리
    #실제 경유횟수에 출발지와 도착지를 고려해야하니 K+2를 해줌.
    minCost = {(i, k): float('inf') for i in range(n) for k in range(K+2)}
    minCost[src,K+1] = 0


    #(비용,현재 노드,남은 경유지 수)
    queue = [(0,src,K+1)]

    #큐가 빌 때까지 반복
    while queue:
        price, node, stop = heapq.heappop(queue)
        #목적지에 도달하면 비용을 리턴한다.
        if node == dst:
            return price

        #남은 경유 횟수 확인
        if stop > 0:
            # graph딕셔너리의 node에서 출발하는 모든 항공편을 순회한다.
            for v, w in graph[node]:
                nextPrice = price + w
                #현재 경로가 이 노드에 도달하기 위한 기존 최소비용(minCost[v])보다 저렴하면 큐에 추가함.
                #또, 현재 경로가 이전 계산된 경로보다 비용이 더 낮거나, 같은 비용으로 더 적은 경유라면, 업데이트해줌.
                if nextPrice < minCost[v,stop-1]:
                    minCost[v, stop-1] = nextPrice
                    heapq.heappush(queue,(nextPrice, v, stop-1))

    #목적지 도달 못한 경우, -1 반환
    return -1

#입력 받는 부분
n = int(input())
flights = json.loads(input())
src = int(input())
dst = int(input())
K = int(input())

print(findCeapestPrice(n, flights, src, dst, K))