1916 - 최소비용 구하기 [Dijkstra]

출처 : 백준 1916 최소비용 구하기

더 많은 문제들에 대한 Python3 풀이는 Github Repo에서 찾아볼 수 있다

문제

1753 - 최단경로 문제와 매우 유사한 문제이다. 1753 최단경로 문제와 같이 방향 그래프 정보와 시작점을 준다는 것이다. 하나 다른 점은 끝나는 점이 주어지고 시작점부터 끝나는 점까지의 거리만 구하면 된는 것이다. 이 문제도 최단거리 구하는 알고리즘 중 가장 많이 사용되는 다익스트라(Dijkstra) 알고리즘을 사용해서 풀었다. 모든 점까지의 거리를 다 구하고나서 마지막에 끝나는 점의 거리만 리턴해서 결과로 출력했다.

Python 리스트의 index는 0부터 시작하기 때문에, 각 노드들에 대한 정보가 주어졌을 때 -1씩 해줬다. 그러고 나서 그래프 노드들에 대한 정보를 다익스트라 알고리즘에 적용했다. 다익스트라 알고리즘은 우선순위 큐를 사용해서 최단거리에 있는 노드를 선택하고 그 노드와 인접된 노드까지의 거리를 계산한다. 계산이 끝나고 현 노드에서 인접한 노드까지의 거리가 최소라면 그 인접한 노드를 우선순위 큐에 추가한다.

다익스트라 알고리즘은 한 노드에서 모든 다른 노드까지의 최단거리를 구하는 알고리즘이다. Python3에서 우선순위큐를 사용하기 위해서 heapq라는 모듈을 import해서 사용했다.

풀이

# BOJ 1916 - 최소비용 구하기
import sys
import heapq
r = sys.stdin.readline
INF = 1e9


def dijkstra(n, s, e, edg):
    q = []
    dist = [INF] * n
    dist[s-1] = 0
    heapq.heappush(q, [s-1, 0])

    while q:
        pos, cost = heapq.heappop(q)

        for p, c in edg[pos]:
            c += cost
            if c < dist[p]:
                dist[p] = c
                heapq.heappush(q, [p, c])
    return dist[e-1]


N = int(r())
M = int(r())
edges = [[] for _ in range(N)]
for i in range(M):
    u, v, w = list(map(int, r().split()))
    edges[u-1].append([v-1, w])

st, end = map(int, r().split())

print(dijkstra(N, st, end, edges))