[백준/Python] 1753번 - 최단 경로

문제

백준 1753번 - 최단 경로

해결 과정

• 조건

1. 방향그래프
2. 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로

• 우선순위 큐를 이용한 다익스트라 알고리즘 이용
  

풀이

import sys
import heapq

# 정점 n, 간선 m
n,m = map(int,sys.stdin.readline().split())

# 시작 정점의 번호
start = int(sys.stdin.readline())

graph = [[] for _ in range(n+1)]

# [[], [(2, 2), (3, 3)], [(3, 4), (4, 5)], [(4, 6)], [], [(1, 1)]]
# a에서 b로 가는 가중치 c
for i in range(m):
  a,b,c = map(int,sys.stdin.readline().split())
  graph[a].append((b,c))
  
# 무한을 의미하는 INF
INF = int(1e9)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)


def dijkstra(start):
  q  = []
  # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
  # q = [(0, 1)]
  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]))


# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INF)이라고 출력
    if distance[i] == INF:
        print("INF")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])