[BAEKJOON]1753 최단경로 - Python

문제 요약

• 알고리즘 분류: 다익스트라
• 난이도: Gold4
• 문제내용:
  • 시작점 부터 각 노드간의 최단 거리를 구해라.
  • 이동 못할 경우 'INF'를 출력해라

• 사이트: https://www.acmicpc.net/problem/1753

1753번: 최단경로

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 다익스트라 알고리즘알면 풀수 있기때문에 따로 설명은 안하지만 주위 할점은 그래프 초기 설정시 이동시 중복된 노드있기 때문에 dic, dic으로 구조 하면 중복된 값때문에 바뀔수 있기 때문에 dic, list 형식으로 저장하면 맞출수 있을것이다.

Code

Python

import heapq, sys
from collections import defaultdict

input = sys.stdin.readline
INF = float('inf')

def dijkstra(grape, start):
    distances[start] = 0
    queue = []
    heapq.heappush(queue, (distances[start], start))
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if current_distance > distances[current_node]: continue
        
        for node, weight in grape[current_node]:
            distance = current_distance + weight
            
            if distance < distances[node]:
                distances[node] = distance
                heapq.heappush(queue, (distance, node))
                   
V, E = map(int, input().split())
grape = {i : [] for i in range(1, V + 1)}
start = int(input())
distances = {i: INF for i in range(1, V + 1)}

for _ in range(E):
    u, v, w = map(int, input().split())
    grape[u].append((v, w))
    
dijkstra(grape, start)
for i in range(1, V + 1):
    print("INF" if distances[i] == INF else distances[i])