[Algorithm] 프로그래머스 1753 최단경로 | 파이썬 (다익스트라)

※ 1753 최단경로

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

 

문제 해결 TIP

주어진 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는다. 다익스트라 알고리즘으로 구현한다. 우선순위 큐를 초기화하고 큐가 비어있을 때까지 인접 노드를 확인하며 더 짧은 경로를 찾아 해당 거리를 업데이트한다.

 

전체 코드

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    #q = [(0, 1)]

    while q:
        dist, now = heapq.heappop(q)
        #현재 노드가 이미 처리된 노드인지 확인
        if distance[now] < dist:
            continue

        #현재 노드와 연결된 인접 노드 확인
        for i in graph[now]:
            cost =dist + i[1]
            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))


#V == 5일 때 1~5까지 노드가 있는거임.
V, E = map(int,input().split())

snode = int(input()) #시작 노드

graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1) #최단 거리 테이블
#연결 정보 입력
for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))
#graph = [[], [(2, 2), (3, 3)], [(3, 4), (4, 5)], [(4, 6)], [], [(1, 1)]]

dijkstra(snode)

#i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
for i in range(1,V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])