출처

https://www.acmicpc.net/problem/1753

문제

코드

import sys
import heapq

# 중요..
INF = 1e9
input = sys.stdin.readline

def zeroGraph(V):
    return {i:[] for i in range(1,V+1)}

def initGraph(graph,E):
    for _ in range(E):
        start,end,W = map(int,input().rstrip().rsplit())
        graph[start].append((end,W))

def dijkstra(graph,start):
    distance = {i:INF for i in graph}
    distance[start] = 0

    priority_que = [(0,start)]

    while priority_que:
        
        cur_cost,cur_node = heapq.heappop(priority_que)
        
        #현재 노드 오는데 발생한 비용이 이전에 저장된 값보다 크면 갱신 필요 없음
        if cur_cost > distance[cur_node]:
            continue

        #인접 노드 추가, 힙을 이용한 우선 순위 큐를 이용하여 최소 비용을 선택..!
        for neighbor,weight in graph[cur_node]:
            new_distance = cur_cost + weight
            if distance[neighbor] > new_distance:
                distance[neighbor] = new_distance
            heapq.heappush(priority_que,(weight,neighbor))

    return distance

V,E = map(int,input().rstrip().rsplit())
start = int(input().rstrip())

graph = zeroGraph(V)
initGraph(graph,E)
result = dijkstra(graph,start)

for i in range(1,V+1):
    if result[i] == INF:
        print('INF')
    else:
        print(result[i])

다익스트라를 이용하여 최소거리를 구하는 문제. 문제에서 가중치가 양수라고 명시를 해주어서 다익스트라로 문제를 해결하는 것을 빠르게 파악이 가능했지만 계속 오류가 발생해서 많이 힘들었다. ㅠㅠ

틀린 이유

해당 문제의 오류를 찾을 때 아주 오래 걸렸다…

• 무한대의 값을 float(’INF’)로 처리 했을 때 오류가 나는 사실을 알지 못했다…
  • Python에서 float('INF')와 1e9는 모두 큰 값으로 처리되지만, 특정 테스트 케이스에서는 float('INF')와 1e9의 차이가 문제가 될 수 있습니다.
  • 초기 값을 무한대로 하면 무한대 값에서 (양수,음수) 가중치를 더해주어도 그대로 무한대이기 때문에 현재값과 그 전의 값이 비교가 되지 않아서 가중치 값이 갱신되지 않은 것

• 두 노드 사이에 복수의 간선이 존재한다는 사실을 망각하고 코드를 작성했다.
  • 두 노드 사이에 간선이 두 개 있을 때 두 간선이 모두 그래프에 들어가야 하는데 내가 딕셔너리로 구현을 하여 가장 마지막에 들어온 간선의 가중치만 들어왔었다.