G4 1753. 최단경로

문제 보기 :  1753번: 최단경로

---

문제

• 정답률 : 26%

---

작성 코드

import sys
input = sys.stdin.readline

v,e = map(int,input().rstrip().split())
m = int(input().strip()) # 시작 노드

# 그래프 초기화
graph = {i+1:[] for i in range(v)}
for _ in range(e):
    uu,vv,ee = map(int,input().rstrip().split())
    graph[uu].append((vv,ee))

# 최단 거리 테이블 초기화
gg = [float('inf')]*(v+1)
gg[m]=0

import heapq

# 다익스트라 알고리즘
def dijkstra():
    dd = [(0,m)] # (거리, 노드 번호) 순서
    while dd:
        nowdist, nownode = heapq.heappop(dd) 
        
        # 경로값이 전보다 크다면 패스
        if nowdist > gg[nownode]:
            continue

        # 아니라면 인접 노드 확인
        for node,weight in graph[nownode]: 
            newdist = nowdist + weight
            # 더 짧은 경로를 발견하면 업데이트
            if gg[node] > newdist :
                gg[node] = newdist
                heapq.heappush(dd,(newdist,node)) #[2,2]
dijkstra()

for i in gg[1:]:
    print('INF' if i==float('inf') else i)

---

풀이

이 코드는 다익스트라 알고리즘을 사용해 시작 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘이다.

먼저 입력받은 간선 정보를 바탕으로 인접 리스트 형태의 그래프를 구성했다. 이후 최단 거리 테이블을 무한대로 초기화하고, 시작 노드의 거리를 0으로 설정했고 우선순위 큐(heapq)을 사용해 가장 짧은 경로를 가진 노드부터 처리했다.

현재 노드의 인접 노드에 대해, 기존 경로보다 더 짧은 경로가 발견되면 테이블을 업데이트하고 큐에 추가하는데,
모든 노드에 대한 탐색이 끝나면 최단 거리 값을 출력하고. 만약 도달할 수 없는 노드가 있다면 "INF"로 출력하며 마무리했다.