백준 1916 최소비용 구하기 : 파이썬

안녕하세요. 이번엔 다익스트라 기본유형 문제입니다.

간선의 가중치 범위가 0~100,000 사이로 음수는 존재하지 않기 때문에 최단거리( 최소비용 ) 을 구하기 위해 다익스트라 알고리즘을 사용하였습니다.
시간복잡도는 O(VlogV + E)입니다.

저는 풀면서 메모리 초과와 테스트 케이스 오답을 겪었었는데, 원인은 다음과 같습니다.

• 메모리 초과

1. 입력에서 그래프를 vertex(N)와 edge(M)의 최대 수를 고려하지 않고, 이중 딕셔너리 형태로 받았습니다. Ex> (1->2 가중치:3) {1:{2 : 3}}
   N*M 크기를 고려하면 최대 1,000,000,000개의 key들에 대한 해시 테이블이 마련되어야 하는데, 해시테이블 내 충돌(Collision)을 줄이기 위해 이 개수보다 더 많은 영역을 확보해야 하니 이렇게 하면 메모리 초과가 발생합니다.
2. 가중치 업데이트 시, 인접 노드 중 가중치가 낮은 것부터 업데이트를 하기 때문에 최소힙(heapq)를 사용합니다. 이 때, 기존의 가중치보다 낮을 때만 업데이트 하면 되는데 낮거나 같을 때 업데이트를 하게되어 이 최소힙에 더 많은 노드와 가중치정보가 들어갑니다. 1번을 해결하고 나서도 이 문제로 인해 메모리초과가 발생할 수 있습니다.

• 오답

1. 메모리초과 문제 해결 중, 모든 노드의 가중치를 무한대로 초기화 하는 과정 중에 가중치 최대 범위인 100,000으로 초기화를 했을 때 통과하지 못하는 테스트 케이스가 존재합니다. 따라서 그냥 float('int')를 사용해 넉넉히 크게 초기화를 하였습니다.

몇가지 제가 실수했던 부분들을 먼저 기록해놓았습니다. 오류나 테스트 케이스 불합이 발생하면 참고하시면 좋을 것 같습니다.

method

## method
def sol(s, e):
    from collections import defaultdict
    import heapq
    updated_w = defaultdict(lambda : float('inf'))
    updated_w[s] = 0
    
    will_visit = [(updated_w[s],s)]

    while will_visit:
        vw, vn = heapq.heappop(will_visit)

        if updated_w[vn] < vw : continue # 서로 다른 두 정점 내 여러 간선이 존재할 수 있음 : 최적의 최단거리보다 멀 때는 무시

        for adjn, adjw in graph[vn]:
            if vw + adjw < updated_w[adjn] : #부등호 실수...ㅜ
                updated_w[adjn] = vw + adjw
                heapq.heappush(will_visit, (vw + adjw, adjn))
    return updated_w[e]

## input
import sys

input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))
start, end = map(int, input().split())

## output
print(sol(start,end))