## 의사코드 ##
# 주어진 시작점에서 다른 모든 정점으로의 최단 경로 -> 다익스트라
# -> heapq로 구현
# 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리 저장
# 첫 정점의 거리는 0, 나머지는 무한대
# -> distances = {node: float('inf') for node in graph}
# -> distances[start] = 0
# 우선순위 큐에 [거리, 첫 정점] 저장
# -> q = []
# -> heapq.heappush(q, [distances[start], start])
# while q:
# # 우선순위 큐에서 최소 거리를 가진 노드를 pop
# 현재 거리, 현재 노드 = heapq.heappop(q)
# # 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우, 해당 노드와 인접한 노드간의 거리 계산을 하지 않고 skip
# if distances[현재 노드] < 현재 거리:
# continue
# # 주어진 시작점에서 해당 노드로 가는 거리 비교
# for adj, weight in graph[현재 노드].items():
# distance = 현재 거리 + weight
# # 배열에 저장되어 있는 거리보다 주어진 시작점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트
# if distance < distances[adj]:
# # 최단 거리로 업데이트
# distances[adj] = distance
# # 우선순위 큐에 삽입
# heapq.heappush(q, [distance, adj])
# for i in range(1, V+1):
# # 경로가 존재하지 않는 경우 INF 출력
# if distances[i] == float('inf'):
# distances[i] = 'INF'
# print(distances[i])
첫 번째 시도
import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
k = int(input()) # 시작 정점의 번호(start)
# 그래프에 값 입력
graph = {}
for i in range(E):
u, v, w = map(int, input().split())
graph[u].append([v, w]) # [노드, 가중치]
# 시작 정점에서 각 정점까지의 거리 초기화 (무한대)
distances = {node:float('inf') for node in graph}
# 시작 정점의 거리는 0
distances[k] = 0
# 우선순위 큐에 [거리, 시작 정점] 저장
q = []
heapq.heappush(q, [distances[k], k])
while q:
current_distance, current_node = heapq.heappop(q)
if distances[current_node] < current_distance:
continue
for adj, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[adj]:
distances[adj] = distance
heapq.heappush(q, [distance, adj])
for i in range(1, V+1):
if distances[i] == float('inf'):
distances[i] = 'INF'
print(distances[i], end=' ')
-> 런타임 에러
for문으로 출력하는 거니까 end=' '할 필요 없음
통과한 코드
import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
k = int(input()) # 시작 정점의 번호(start)
# 그래프에 값 입력
graph = [[] for i in range(V+1)]
for i in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w)) # [노드, 가중치]
# 시작 정점에서 각 정점까지의 거리 초기화 (무한대)
distances = [float('inf')] * (V+1)
# 시작 정점의 거리는 0
distances[k] = 0
# 우선순위 큐에 [거리, 시작 정점] 저장
q = []
heapq.heappush(q, (distances[k], k))
while q:
# 우선순위 큐에서 최소 거리를 가진 노드를 pop
current_distance, current_node = heapq.heappop(q)
# distances에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우, 해당 노드와 인접한 노드간의 거리 계산을 하지 않고 skip
if distances[current_node] < current_distance:
continue
# 주어진 시작점에서 해당 노드로 가는 거리 비교
for adj, weight in graph[current_node]:
distance = current_distance + weight
# distances에 저장되어 있는 거리보다 주어진 시작점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트
if distance < distances[adj]:
# 최단 거리로 업데이트
distances[adj] = distance
# 우선순위 큐에 삽입
heapq.heappush(q, (distance, adj))
for i in range(1, V+1):
# 경로가 존재하지 않는 경우 INF 출력
if distances[i] == float('inf'):
distances[i] = 'INF'
print(distances[i])
-> graph와 distances를 길이가 정해진 리스트로 구현
-> 튜플로 삽입: 메모리 68224 KB / 시간: 700 ms
cf) 배열에 튜플이 아닌 리스트로 삽입하는 경우
-> 리스트로 삽입: 메모리 73388 KB / 시간: 912 ms
=> 튜플이 더 빠름
graph 입력 예시
# graph 입력 예시
V = 5
graph = [[] for i in range(V+1)]
graph[5].append((1, 1))
graph[1].append((2, 2))
graph[1].append((3, 3))
graph[2].append((3, 4))
print('graph:', graph)
print('graph[5]:', graph[5])
"""
graph: [[], [(2, 2), (3, 3)], [(3, 4)], [], [], [(1, 1)]]
graph[5]: [(1, 1)]
"""
다른 풀이
import sys
input = sys.stdin.readline
import heapq
INF = int(1e9) # 무한대의 값으로 10억 설정
def dijkstra():
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]))
# 노드의 개수, 간선의 개수
n, m = map(int, input().split())
# 시작 노드
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c
graph[a].append((b, c))
# 다익스트라 알고리즘 수행
dijkstra()
# 각 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
if distance[i] == 1e9:
print('INF')
else:
print(distance[i])