[BOJ] 1916번 최소비용 구하기 / 사용언어 : 파이썬(python)

※ 문제링크 

1916번: 최소비용 구하기

해당 문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 따로 추가할 조건 없이 해당 알고리즘만 사용하면 풀 수 있는 문제였기에 문제해결은 많이 어렵지는 않았다. 다만, 중간에 조건 1개를 추가해주어야 했기에 해당 조건을 구상하는데 시간이 걸린 문제였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 리스트를 활용하여 그래프를 구현한다.

2. heapq를 활용하여 우선순위 큐를 구현한 후 특정 정점에서 다른 정점으로 이동할때의 최단경로를 구하고 갱신할 함수를 작성한다.

3. 경유할 정점으로 갈 때 걸리는 시간이 dp에 저장된 값보다 클 경우 반복문을 실행하지 않는다는 조건을 작성한다.

4. 입력받은 출발점과 도착점을 이용하여 결과값을 출력한다.

 

import sys
import heapq

# input = sys.stdin.readline
N = int(input()) # 도시의 개수
M = int(input()) # 버스(노선)의 개수
graph = [[] for _ in range(N+1)]
for _ in range(M):
    s, e, wei = map(int, input().split())
    graph[s].append([wei, e])
start, end = map(int, input().split())

def dijkstra(start):
    heap = []
    dp = [float('inf') for _ in range(N+1)]
    dp[start] = 0
    heapq.heappush(heap, [0, start])

    while heap:
        wei, n = heapq.heappop(heap)
        if wei > dp[n]:
            continue
        for wei_n, n_e in graph[n]:
            n_w = wei + wei_n
            if dp[n_e] > n_w:
                dp[n_e] = n_w
                heapq.heappush(heap, [n_w, n_e])

    return dp
ans = dijkstra(start)
print(ans[end])

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.