[BOJ] 11779번 최소비용 구하기 2 / 사용언어 : 파이썬(python)

※ 문제링크

11779번: 최소비용 구하기 2

해당 문제는 가중치가 있는 최단거리경로를 구하는 것과 관련된 문제로 가중치에 음수가 없으므로 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제였다. 다만 경유하는 도시들의 숫자와 도시들을 같이 출력해줘야하는 것이 문제조건이기에 해당 부분만 추가하면 생각보다 쉽게 해결할 수 있는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 바탕으로 리스트를 활용하여 그래프를 구현해준다.

2. heapq와 동적프로그래밍 개념을 사용하여 최단거리를 구할 다익스트라 알고리즘의 토대를 쌓고, 가중치, 도착도시, 경유도시목록을 기록 및 갱신할 수 있게 약간 변형하여 함수를 작성한다.

3. 반복문이 종료되면 도착도시의 최단경로, 경유한 도시의 수, 경유한 도시목록을 출력해준다. 

+ 시간 단축을 위해 sys를 사용해주었다.

 

from heapq import heappush, heappop
import sys

# input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, c = map(int, input().split())
    graph[s].append([c, e])
start, end = map(int, input().split())

def dijkstra(start, end):
    heap = []
    dp = [float('inf') for _ in range(n+1)]
    cities = [[] for _ in range(n+1)]
    dp[start] = 0
    cities[start] = [start]
    heappush(heap, [0, start, [start]])

    while heap:
        cost1, cp1, city = heappop(heap)
        if dp[cp1] < cost1: # 해당부분이 빠지면 시간초과가 뜨니 유의해주세요.
            continue
        for cost2, cp2 in graph[cp1]:
            cost_n = cost1 + cost2
            if cost_n < dp[cp2]:
                dp[cp2] = cost_n
                cities[cp2] = city + [cp2]
                heappush(heap, [cost_n, cp2, city + [cp2]])
   
    print(dp[end])
    print(len(cities[end]))
    print(*cities[end])
    return 

dijkstra(start, end)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.