[CLASS 4]백준 1753번 - 최단경로

1753번 : 최단경로

 

오랜만에 보는 다익스트라 문제이다. 기본적인 다익스트라를 구현할 수 있다면 해결할 수 있다.

 

 다익스트라에서 시작점에서 가장 가까운 점을 선택할 때 우선순위 큐를 이용하면 효율적으로 선택할 수 있다.

 

우선순위 큐는 파이썬의 내장모듈 heapq를 사용하면 최소 힙을 바로 사용할 수 있어 편리하다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
import heapq
input = stdin.readline

# 입력
V, E = map(int,input().split())
nodes = [[] for _ in range(V+1)]
# 시작점
start = int(input())
for _ in range(E):
    u,v,w = map(int,input().split())
    nodes[u].append((v,w))

dist = [1e9] * (V+1)
dist[start] = 0

# 가장 가까운 노드를 찾기 위한 힙
queue = []
heapq.heappush(queue,(0,start))

while queue:
    d, now = heapq.heappop(queue)
    # 이미 더 가까운 경로를 찾았다면 넘김
    if dist[now] < d:
        continue
    for dest, w in nodes[now]:
        cost = d + w
        # 더 가까운 경로를 찾았다면
        if cost < dist[dest]:
            dist[dest] = cost
            heapq.heappush(queue,(cost,dest))

# 출력
print('\n'.join([str(i) if i != 1e9 else 'INF' for i in dist[1:]]))

 

다익스트라 알고리즘을 파이썬으로 구현하는데 나동빈 님의 유튜브 강의가 많은 도움이 되었다. 그림으로 자세하게 설명해 주셔서 다익스트라 알고리즘을 잘 모르겠으면 한번쯤 보는게 좋을 것 같다.