[Python] 백준 11779번 최소비용 구하기 2 - 다익스트라 알고리즘 최단경로 구하기

🥇문제 링크

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

 

📎알고리즘

난이도: Gold3 

그냥 다익스트라를 사용했다면 실버 난이도였겠지만 골드 문제답게 경로 출력을 추가로 시켜서 난이도가 확 올라간 모습이다.

 

기본적으로 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 이용해 주면 된다.

시간 복잡도를 O(N^2)에서 O(NlogN)으로 줄이기 위해 우선순위 큐(파이썬에서는 heapq)를 사용해 주었다.

 

쉽게 생각하면 최솟값으로 업데이트할 때만 전 노드 값을 저장해 주고 마지막에 출력해 줄 때,

가장 마지막 노드에서 저장된 값을 통해서 되추적해 올라가 역순으로 출력해 주면 경로가 된다.

 

참고: *list는 unpacking 문법이다. 응용해서, *list [::-1]를 통해서 리스트의 가장 마지막 원소부터 공백을 넣어 출력할 수 있다. 

 

⌨코드

import sys
import heapq

if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(input())
    m = int(input())

    arr = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b, c = map(int, input().split())
        arr[a].append((b, c))

    prev_node = [0] * (n + 1)
    x, y = map(int, input().split())
	
    #다익스트라 알고리즘
    def dijkstra(start):
        distances = [1e9] * (n + 1)
        distances[start] = 0
        q = []
        heapq.heappush(q, [distances[start], start])

        while q:
        	#최단 거리가 가장 짧은 노드 정보 꺼내기
            dist, node = heapq.heappop(q)

            # 밑에 for문에서 distances[node]값이 갱신될 수 있음
            # 현재 노드가 이미 처리된 적이 있는 노드라면 처음 처리한게 항상 최단거리이므로 무시
            if dist > distances[node]:
                continue
			
            #현재 노드와 연결된 인접 노드 확인
            for n_node, n_dist in arr[node]:
                distance = dist + n_dist
                
                #현재 노드를 거쳐서 다음 노드로 이동하는 거리가 더 짧은 경우
                if distance < distances[n_node]:
                    distances[n_node] = distance
                    #이전 노드로 경로 저장
                    prev_node[n_node] = node
                    heapq.heappush(q, [distance, n_node])

        return distances

    min_cost = dijkstra(x)
    print(min_cost[y])
	
    #최단거리 역추적
    z = y
    path = []
    while True:
        if z == x:
            break
        path.append(z)
        z = prev_node[z]
    print(len(path) + 1)
    print(x, *path[::-1])

💻제출결과

첫번째는 바보같이 플로이드-와샬로 구현...