1. 문제 설명

최단경로

2. 문제 분석

다익스트라 알고리즘을 통해 특정 노드에서 다른 모든 노드까지의 최단 경로를 구한다. 우선순위 큐(힙 구현)를 통해 시간 복잡도를 줄일 수 있다.

1. 연결 노드 및 비용을 통해 그래프를 구현한다.
2. 초기 상태에서 시작 노드를 제외한 나머지 노드는 갈 수 없다고 취급하자. 즉 INF다. 자기 자신에 대한 거리는 0이다.
3. 현재 시작 노드와 해당 노드 간의 거리 대 우선순위 큐에서 팝되는 노드로 갈 수 있는 비용을 비교해, 이 상황에서의 최단 경로를 업데이트하자.
4. 다른 모든 노드에 대한 최단 경로를 구할 수 있다.

• 우선순위 큐를 사용한다면 시간 복잡도를 $O(N^2)$에서 $O(N*log N)$까지 줄일 수 있다는 데 주목하자.

3. 나의 풀이

import heapq

v, e = map(int, input().split())
k = int(input())
nodes = [[] for _ in range(v+1)]

for _ in range(e):
    tail, head, weight = map(int, input().split())
    nodes[tail].append([head, weight])
    # 방향 그래프
INF = 10000000
# 이동할 수 없다면 거리는 무한대로 취급
distances = [INF for _ in range(v+1)]
distances[k] = 0
# 초기 상태에서 자기 자신을 제외한 나머지 노드는 갈 수 없음(거리 무한).

queue = []
heapq.heappush(queue, [0, k])
# 큐에 [현재 노드까지의 비용 ,현재 노드]을 입력한다.

while queue:
    cur_cost, cur_node = heapq.heappop(queue)

    for next_node, next_cost in nodes[cur_node]:
        if distances[next_node] > next_cost + cur_cost:
            # 지금 갈 수 있는 방법보다 짧은 루트가 존재한다면
            distances[next_node] = next_cost + cur_cost
            heapq.heappush(queue, [next_cost+cur_cost, next_node])
            # 간선 저보를 업데이트하고, 이를 활용할 수 있도록 큐에 넣어서 다른 연결 지점에서도 사용하자.

for distance in distances[1:]:
    if distance == INF: print('INF')
    else: print(distance)
    # 끝까지 갈 수 없는 무한 거리는 INF로 대신 출력한다.