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

https://www.acmicpc.net/problem/1753

 

 

시작 노드를 주면, 해당 노드로부터 나머지 노드까지의 거리를 구하는 문제이다.

해당 문제를 보자마자 다익스트라 알고리즘을 사용하면 쉽게 풀 수 있겠다는

생각이 들었다.

 

# 다익스트라 풀이과정

1. 시작 노드로부터 각 노드까지의 최단 거리를 구하는 문제임

2. 다익스트라 알고리즘 사용

3. 최소힙을 사용하여 짧은 경로 순으로 뽑아내서 사용

4. 각 간선을 순회하면서 기존보다 짧아지는 경로가 있으면 해당 거리를 업데이트

5. 짧아진 경로의 목적지와 거리를 튜플로 묶어서 최소힙에 넣어줌

6. 위 과정을 반복

7. 더 이상 짧아지는 경로가 없으면 순회를 종료하고 출력

 

 

[다익스트라 알고리즘을 이용한 코드 - 성공]

# ex_1753
import sys
import heapq
V,E = map(int,sys.stdin.readline().split())
K = int(sys.stdin.readline())
graph = [[] for _ in range(V+1)]
for _ in range(E):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append((b,c))

# V번 노드로부터 각 노드까지의 거리를 저장한 배열
distance = [1e8 for _ in range(V+1)]
distance[K] = 0
heap = []
heapq.heappush(heap,(0,K))

# 다익스트라 알고리즘
def dijkstra():
    while heap:
        d,start = heapq.heappop(heap)
        if distance[start] < d:
            continue
        for tup in graph[start]:    # tup : 출발 노드별 간선
            now_d = tup[1]+d
            if now_d < distance[tup[0]]:
                distance[tup[0]] = now_d
                heapq.heappush(heap,(now_d,tup[0]))

dijkstra()

# 출력
for x in distance[1:]:
    if x == 1e8:
        print('INF')
    else:
        print(x)

 

확실히 모든 지점까지의 최단거리를 구하는 것은 다익스트라 알고리즘을

사용하는 것이 가장 효율적인 것 같다.