[BOJ / PYTHON] 1753. 최단 경로

import heapq

INF = 10 ** 10

V, E = map(int, input().split())

K = int(input())

d = [INF] * (V+1)

q = list([] for _ in range(V+1))

for i in range(1, E+1):
    s, e, w = map(int, input().split())

    heapq.heappush(q[s], (w, e))

def dijkstra(start):
    d[start] = 0

    pq = []

    heapq.heappush(pq, (0, start))

    while len(pq) != 0:
        current = pq[0][1]

        weight = pq[0][0]

        heapq.heappop(pq)

        if d[current] < weight:
            continue

        for i in range(len(q[current])):
            next = q[current][i][1]
            next_weight = weight + q[current][i][0]

            if next_weight < d[next]:
                d[next] = next_weight
                heapq.heappush(pq, (next_weight, next))

dijkstra(K)

d = d[1:]

for i in d:
    if i == INF:
        print("INF")
    else:
        print(i)

# 가장 쉬운 방법으로 다익스트라 알고리즘을 구현하기
#
# graph = list([INF] * V for _ in range(V))
# visited = [False] * V
# d = [0] * V
# for _ in range(E):
#     s, e, w = map(int, input().split())
#
#     graph[s - 1][e - 1] = w
#     graph[s - 1][s - 1] = 0
#
# def get_small_idx():
#     global  graph, d
#     min_weight = INF
#     index = 0
#
#     for i in range(V):
#         if d[i] < min_weight and not visited[i]:
#             min_weight = d[i]
#             index = i
#
#     return index
#
#
# def dijkstra(start):
#     global graph, d
#     for i in range(V):
#         d[i] = graph[start][i]
#
#     visited[start] = True
#
#     for i in range(V):
#         current = get_small_idx()
#         for j in range(V):
#             if not visited[j]:
#                 if d[current] + graph[current][j] < d[j]:
#                     d[j] = d[current] + graph[current][j]
#
#
# dijkstra(K - 1)
#
# for i in d:
#     if i == INF:
#         print("INF")
#     else:
#         print(i)

풀이.

동빈나 쌤의 강의를 보면서 해결했다.
DFS 로는 메모리 초과 발생.
따라서, 다익스트라 알고리즘을 사용한다.
가장 기초적인 방법인 선형 탐색 다익스트라 구조는 메모리 초과와 더불어 시간 초과가 발생한다.
메모리 초과를 해결하기 위해 불필요한 배열의 크기를 줄여야 하므로, visited 를 삭제한다.
따라서, 최소 힙 / 우선순위 큐 형태의 인접 리스트 다익스트라 알고리즘을 구현한다.

1. 선형 탐색 다익스트라 알고리즘
   

2. 인접 리스트 다익스트라 알고리즘