[Python] [BOJ] 최단경로(1753)

💡 문제 해결

1. 각 간선은 단방향 간선으로 각 노드에 대한 정보를 dict로 저장
2. 노드별로 거리 정보를 저장할 dict를 출발지를 제외하고 최대값으로 설정
3. 거리별로 정렬될 수 있도록 heap트리를 사용
4. 탐색할 노드와의 거리를 최소값으로 갱신
5. 각 노드와의 거리를 출력

📌 해당 문제는 노드와 간선이 많으므로 heap을 사용, heap을 사용하지 않으면 시간초과
📌 주석 처리된 코드를 추가하면 조금 더 빠른 속도로 탐색 가능

🧾 문제 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 
단, 모든 간선의 가중치는 10 이하의 자연수이다.

문제보기

🖨 입출력

📝 풀이

import sys
import heapq
from collections import defaultdict

V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())
lines = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

nodes = defaultdict(list)
for line in lines:
    nodes[line[0]].append((line[1], line[2]))

distance = {i: float('inf') if i != K else 0 for i in range(1, V + 1)}
heap = []
heapq.heappush(heap, (0, K))
while heap:
    current_dis, current_node = heapq.heappop(heap)
    # if distance[current_node] < current_dis: continue
    for next_node, dis in nodes[current_node]:
        if distance[next_node] > distance[current_node] + dis:
            distance[next_node] = distance[current_node] + dis
            heapq.heappush(heap, (distance[next_node], next_node))

for val in distance.values():
    if val == float('inf'):
        print('INF')
    else:
        print(val)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/1753