[알고리즘] 백준1735 최단경로 - 파이썬

내일 코테를 앞두고 백준에서 최단경로 알고리즘 문제를 풀어보았다. 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 문제인데 내일 이런 문제 한 문제만 나오길 빌면서..

 

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

1753번: 최단경로

 

 

[풀이 코드]

from sys import stdin
import heapq

INF = 300000
input = stdin.readline

v, e = map(int, input().split())
start = int(input())

distance = [INF] * (v + 1)
graph = [[] for i in range(v+1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def solution(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

solution(start)

for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

- 역시나 이코테에서 다룬 코드를 쓰면 되는데 처음엔 이해가 잘 안돼서 손 코딩으로 열심히 이해하면서 암기했다..!

- 우선순위 큐를 활용하는게 훨씬 코드가 간결해진다.