[boj 1916][Python] 최소비용 구하기

링크

문제에서 바라는 것이 잘 보이는, 구현 적용 문제였다.

오늘은 다익스트라 알고리즘 적용하였고, 플로이드-워셜 알고리즘도 적용해볼 예정이다.

그래프를 딕셔너리로 관리하기

그래프를 딕셔너리로 관리한다. 입력 받기가 헷갈려서, 따로 포스팅으로 정리하였다.

중첩 딕셔너리 - dict in dict

맞왜틀

이 문제의 경우 단순히 알고리즘 적용만 하는 것이라 생각했기 때문에 당황했다.

이런 반례가 있다.

2
2
1 2 10
1 2 20

• 반례 출처: kgstiger님 / 링크

확인해보니 나중 값으로 그래프 값이 덮어씌워진다.

최단 경로를 찾는 것이기 때문에, 이미 해당 start, end에 해당하는 값이 존재한다면 검사 후 작을 때만 갱신한다.

for _ in range(m):
    start, end, cost = map(int, input().split())
    if end in graph[start].keys():
        # 이미 있으면 작은 경우에만 바꿈
        if graph[start][end] > cost:
            graph[start][end] = cost
    else:
        graph[start][end] = cost

input = sys.stdin.readline

이걸 안 써 줬더니 시간초과 나서 고쳤다. 통과!

내일은 플로이드-워셜 풀이법도 이 게시물에 덧붙여 보겠다.

코드

# 1916 최소비용 구하기
# (1) 다익스트라 이용하여 

import sys
import heapq

INF = sys.maxsize
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = {}
for i in range(n+1):
    graph[i] = {}

for _ in range(m):
    start, end, cost = map(int, input().split())
    if end in graph[start].keys():
        # 이미 있으면 작은 경우에만 바꿈
        if graph[start][end] > cost:
            graph[start][end] = cost
    else:
        graph[start][end] = cost

start, end = map(int, input().split())

d = [INF] * (n+1)

def dijkstra(graph, start):
    d[start] = 0
    queue = []
    heapq.heappush(queue, [d[start], start])
    # 시작노드 탐색을 위해 초기화

    while queue:
        cur_d, cur_dest = heapq.heappop(queue)

        if d[cur_dest] < cur_d:
            continue

        for new_dest, new_d in graph[cur_dest].items():
            tmp_d = cur_d + new_d   # 거쳐가는 거리
            if tmp_d < d[new_dest]:
                # 현재 최단거리보다 거쳐가는게 더 가까움.
                d[new_dest] = tmp_d   # 최단거리 갱신
                heapq.heappush(queue, [tmp_d, new_dest])
    
    return d

dijkstra(graph, start)

print(d[end])