백준 1753. 최단 경로

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

1753번: 최단경로

 

코드

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

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

    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, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

dijkstra(start)

for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

 

다익스트라 기본 문제였다.

 

heapq를 사용하기 위해 q 리스트를 생성하고 (거리, 시작노드번호)를 튜프로 묶어 힙큐에 넣어준다.

 

최단거리테이블[시작노드]를 0으로 초기화해주고

q가 빌 때까지 반복한다

 

큐에서 거리와 노드번호를 꺼낸 후

꺼낸 거리 값이 최단 거리 테이블에 기록된 정보보다 값이 크면 최단 정보가 아니기 때문에 continue로 무시하고

그게 아니라면 최단 거리 정보임으로 아래의 작업을 수행한다.

 

꺼낸 노드 번호에서 갈 수 있는 노드와 거리 정보를 이용해

cost값이 최단 거리 테이블의 거리 정보보다 작으면, 업데이트 하고 힙큐에 넣어준다.

 

위 과정을 반복하면 방문할 수 있는 노드에 대하여 최단거리테이블이 모두 갱신된다.

 

 

참고 자료

https://jie0025.tistory.com/199