1916. 최소비용 구하기

문제

백준 1916번 최소비용 구하기

---

풀이

처음에는 dfs를 사용하여 코드를 작성했다.
주어진 예제의 경우는 n이 작기 때문에 잘 동작했는데 채점을 돌려보니 RecursionError로 런타임 에러가 발생했다.

def dfs(L, val):
    global res
    if L != des and len(city[L]) == 0: return
    if val >= res: return
    if L == des:
        if val < res: res = val
    else:
        for i in range(len(city[L])):
            dfs(city[L][i], val + cost[L][city[L][i]])

if __name__ == '__main__':
    n = int(input())
    m = int(input())
    city = [[] for _ in range(n+1)]
    cost = [[1000 for _ in range(n+1)] for _ in range(n+1)]
    for _ in range(m):
        s, d, v = map(int, input().split())
        city[s].append(d)
        cost[s][d] = v
    src, des = map(int, input().split())
    res = 1e9

    dfs(src, 0)
    print(res)
    

이 문제는 한 노드에서 다른 노드로 가는 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하면 탐색 시간이 훨씬 개선된다.
(추가로, 그래프를 딕셔너리로 저장해서 더 직관적으로 사용할 수 있도록 했다.)

import heapq as hq

n = int(input())
m = int(input())
adj = {city:{} for city in range(1, n+1)}
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a][b] = c
src, dest = map(int, input().split())

cost = {city:int(1e9) for city in range(1, n+1)} # 거리 무한대로 초기화
cost[src] = 0 # 출발 노드는 0
q = []
hq.heappush(q, (0, src)) # 출발 노드 삽입
while q:
    val, current = hq.heappop(q)
    if val > cost[current]: continue # 기존의 거리보다 길면 고려할 필요 없음
    for nxt, v in adj[current].items(): # 인접노드 탐색
        if v + val < cost[nxt]: # 기존의 거리보다 짧으면 갱신
            cost[nxt] = v + val
            hq.heappush(q, (v + val, nxt)) # 다음 노드의 인접노드 탐색을 위해 큐에 삽입
print(cost[dest])

---

부족한 점

다익스트라 알고리즘 동작 과정을 설명할 수 있도록 할 것
(+다른 최단 경로 알고리즘에 대해서도)