1753: 최단경로

풀이 시간

• 39m
• dijkstra 알고리즘을 그대로 구현하는 문제였다

구현 방식

• 처음에 각 노드마다 bfs를 순회하는 방식으로 구현하려했으나 시간초과가 발생했고, 알고리즘 분류를 보고 dijkstra 알고리즘을 사용해야한다는 사실을 알게되었다
• dijkstra: 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
• 최소 힙을 이용하여 힙이 빌때까지 최단 거리가 가장 짧은 노드를 꺼내고 기존의 거리보다 작으면 최단 거리를 갱신해주는 방식으로 진행 (인접 노드들도 같은 방식으로 진행)

코드

import sys
import heapq

def dijkstra(start):
    global distances
    distances[start] = 0

    heap = []
    heapq.heappush(heap, [distances[start], start])

    while heap:
        curr_distance, curr_dest = heapq.heappop(heap) #최단 거리가 가장 짧은 노드 꺼냄
        if distances[curr_dest] < curr_distance:
            continue

        for new_dest, new_distance in graph[curr_dest]:
            distance = curr_distance + new_distance
            if distance < distances[new_dest]:
                distances[new_dest] = distance
                heapq.heappush(heap, [distance, new_dest])
    
V, E = map(int, sys.stdin.readline()[:-1].split()); K = int(sys.stdin.readline()[:-1])

graph = [[] for _ in range(V+1)]
for e in range(E):
    u, v, w = list(map(int, sys.stdin.readline()[:-1].split()))
    graph[u].append((v, w))

distances = dict()
for v in range(1, V+1):
    distances[v] = int(10e9)

dijkstra(K)

for key, value in distances.items():
    if value == int(10e9):
        print("INF")
    else:
        print(value)

결과