0528_백준 1753번 : 최단경로/ 다익스트라(Dijkstra) 알고리즘/ Python

[문제 풀이]

✔ 주어진 시작점에서 모든 정점으로의 최단 경로 값을 구하는 문제 => 다익스트라(dijksta) 알고리즘 활용

✔ 우선순위큐를 활용하기 위해  heapq 모듈을 불러와 사용함 (heappop, heappush 사용)

✔heapq 모듈 특성상, pop하게 되면 가장 작은 값을 가진 원소가 리턴되기 때문에 힙에 원소를 저장할 때 '경로값(cost), 노드(node)' 순으로 넣어야 다익스트라 알고리즘에서 원하는 결과를 얻을 수 있다. 왜냐면 경로값을 기준으로 최단 경로를 찾아 나가야 하는 로직이기 때문이다. 처음에 이 부분을 간과하여 노드, 경로값 순으로 넣었다가 계속해서 에러가 발생했다. (도움주신 덕봇기님 감사합니다😁🙌)

 

[코드 구현]

import heapq
import sys
input = sys.stdin.readline

def dijkstra(v, k, adj):
    q = []
    dist = [INF]*(v+1) # 최단 경로 저장하는 리스트
    dist[k] = 0 # 시작 위치는 경로값이 0
    heapq.heappush(q, [0, k])

    while q:
        cost, node = heapq.heappop(q) # heapq 성질을 이용해, 경로값이 가장 작은 노드를 가져온다
        for n, c in adj[node]: # 인접한 노드의 경로값을 살펴보고
            c += cost
            if c < dist[n]: # 기존 저장돼 있는 경로값과 비교하여
                dist[n] = c # 더 작은 경우에만 저장하는 경로값 갱신하고
                heapq.heappush(q, [c, n]) # heapq에 push
    return dist

V, E = map(int, input().split())
k = int(input())
adj = [[] for _ in range(V+1)]
INF = float('inf') # 무한대 값 가져옴

# 인접리스트 생성
for i in range(E):
    u, v, w = map(int, input().split())
    adj[u].append([v, w])

for i in list(dijkstra(V, k, adj))[1::]:
    print(i if i != float('inf') else 'INF')

[문제 출처]

백준 1753번 최단경로 https://www.acmicpc.net/problem/1753

1753번: 최단경로