백준 1753 : 최단경로 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(Node):

    dp[Node]=0

    heapq.heappush(heap,(0,Node))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:

                dp[next_node]=next_value
                heapq.heappush(heap,(next_value,next_node))


INF=int(1e9)

V,E=map(int,input().split())
K=int(input())
dp=[INF]*(V+1) ; heap=[] ; graph=[ [] for _ in range(V+1) ]

for _ in range(E):
    u,v,w=map(int,input().split())
    graph[u].append((w,v)) # 가중치 먼저

Dijkstra(K)

for i in range(1,V+1):

    if dp[i]==int(1e9):
        print("INF")
    else:
        print(dp[i])

📌 어떻게 접근할 것인가?

아주 기본적인 다익스트라 문제입니다.
dp 배열에 INF 값을 넣은후에 heap 자료구조를 써서 간선의 비용이 적은 노드부터 탐색해주고 노드들의 이동거리의 최소값을 매번 갱신해주었습니다.

이때 경로가 존재하지 않을 수 있기 때문에 dp 배열의 초기값과 같다면 INF 를 출력해주고 그렇지 않다면 배열의 값을 출력해줍니다.