[G4] 백준 1753 - 최단경로 (Python3)

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

1753번: 최단경로

---

해결방법

다익스트라 알고리즘을 활용하여 풀었다.

풀이👀

나는 그래프를 python의 dictionary로 표현했다. 그래서 입력받은 간선의 정보들을 모두 graph에 담았다.

* 하지만 이렇게 되면 쓸모없는 데이터까지 받아오게 된다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 라는 문제 조건이 있기 때문이다.

모든 정보를 담아서 풀이해내도 다익스트라 알고리즘의 특성상 더 적은 값으로 결과값이 정해지므로 상관은 없지만 만약 메모리 제한이 적을 때는 어떻게 해결하면 좋을지 고민이 되었다.

 

(graph를 표현하는 방법은 list로도 가능하다. graph를 2차원 list로, distances는 1차원 list로 두고 풀 수 있다.)

---

코드🐱‍👓

import heapq

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

INF = float('inf')
graph = {i: [] for i in range(1, V + 1)}

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]

distances = {node: INF for node in graph}
distances[start] = 0

# [[시작점에서 노드까지 가는 거리, 노드]]
queue = [[distances[start], start]]

while queue:
    current_distance, current_node = heapq.heappop(queue)
    if current_distance < distances[current_node]:
        continue
    for next_destination, next_distance in graph[current_node]:
        distance = next_distance + current_distance
        if distance < distances[next_destination]:
            distances[next_destination] = distance
            heapq.heappush(queue, [distance, next_destination])

for node in distances:
    print("INF" if (k := distances[node]) == INF else k)

---