[백준] 1753. 최단경로

 

📌문제

1753번: 최단경로

 

🎖️난이도

 

✔️풀이

# 다익스트라 & 인접리스트 => sigle source, 양수 간선 존재
import heapq
import sys
input = sys.stdin.readline # 안해주면 시간초과
INF = int(1e9) 

v, e = map(int, input().split())
start = int(input())
graph = {i : [] for i in range(1, v+1)}
dist = [INF] * (v+1) # 최단거리 테이블

for _ in range(e):
    src, dst, w = map(int, input().split())
    graph[src].append((dst, w))

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start)) # (0, 1) : (최단거리, 노드번호)
    dist[start] = 0
    
    while queue:
        cost, now = heapq.heappop(queue) # (0, 1)
        
        # 방문하지 않아도 되는 노드 예외처리
        if cost > dist[now]:
            continue
        
        # 방문하지 않은 노드의 인접 노드들 탐색 (최단거리 갱신)
        for child in graph[now]:
            new_cost = cost + child[1] # child : (2, 2)
            if new_cost < dist[child[0]]:
                dist[child[0]] = new_cost
                heapq.heappush(queue, (new_cost, child[0]))
                
dijkstra(start)

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

 

🧠노트

가중치의 값들이 다양한 양수로 이루어졌고, single source 최단경로이므로 Dijkstra로 풀이하면 된다.

 

시작점(start)으로부터 다른 모든 정점까지의 최단 거리를 탐색하며 최단거리 테이블(dist)에 갱신한다.

이때, 최소힙(heapq)를 이용한 우선순위 큐를 통해 노드(최단거리, 노드번호)를 하나씩 pop, push하면 된다.

 

cf. 우선순위 큐(heapq)를 이용해 최단거리 테이블 값이 작은 노드부터 pop하는 이유?

• 속도에 이점이 있기 때문에!
• 그냥 큐 써도 결과는 같지만, 우선순위 큐를 통해 노드 꺼내는 횟수 및 최단거리 값 갱신 횟수가 줄어든다.
• 이전에 계산해둔 값(최단거리 테이블 값)이 최솟값을 보장하므로!

 

cf. 핵심 코드

# 방문하지 않아도 되는 노드 예외처리
if cost > dist[now]:
    continue

방문한 적 있는지 체크 (방문할 필요 없다면 pass) 

위의 예외처리 안하고 모든 노드의 인접 노드들을 탐색해도 상관은 없음.

하지만,

아래 for문에서 pop한 노드를 거쳐서 다른 인접 노드값까지 더할 필요가 없으므로

pop한 노드의 cost가 최단거리 테이블 값(최단거리)보다 크다면 pass!

 

 

🔍참고

-