[백준] 1753번 : 최단경로 (파이썬)

Dijkstra 문제 

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

1753번: 최단경로

 

(1) 처음에 실패한 이유

 

(1) 처음엔 distance[start] = 0 이부분을 빼뜨려서 dijkstra 로직이 동작하지 못했다. 즉, distance 벡터를 출력했을 때 값이 모두 최댓값으로 나오는 문제가 있었다.

[10001, 10001, 10001, 10001, 10001] 이런식으로 나왔었음.

 

(2) 두번째로는 distance 벡터 초깃값을 설정해주는데에서 문제가 있었다. --> 이거 때문에 계속 2%에서 틀렸었음.

파이썬에서 최댓값으로 초기화를 해줘야 하는데 찾아보기 귀찮아서 대충 distance = [10001] * (node + 1) 이렇게 10001이라는 값으로 초기화해주었다. 문제에 입력을 보면 node의 weight가 10 이하이길래 저렇게 해도 문제가 없겠지 했지만 vertex와 edge의 갯수가 (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 다음과 같이 상당히 큰 값이다. 따라서, 이웃된 노드들을 타고타고 들어가 edge의 weight를 누적합시키다보면 10001이라는 값은 훌쩍 넘겨버리기 때문에 여기서 문제가 발생한 것이다.

역시 찾아보기 귀찮아서 이렇게 최댓값도 대충 때려박으면 바로 오답이 나온다.

따라서 10001 대신 100000001로 초기화값을 바꿔주니까 정답이 나왔다. 어지간히 파이썬 최댓값 초기화 방법을 찾아보기 귀찮았나보다.

 

(2) 수정한 내 코드 (성공)

# 최단경로 (골드 4)
import sys
import heapq
node,e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
graph = [[] for _ in range(node + 1)]
for _ in range(e):
    u,v,w = map(int, sys.stdin.readline().split())
    graph[u].append((v,w))

def dijkstra(start, graph):
    heap = [(0, start)]
    distance = [100000001] * (node + 1) # (2) 최댓값 초기화 주의 필요
    distance[start] = 0 # (1) 시작할 때 필요

    while heap:
        curr_dist, u = heapq.heappop(heap)
        if distance[u] < curr_dist: continue
        for v, weight in graph[u]:
            if distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                heapq.heappush(heap, (distance[v], v))
    return distance
distance = dijkstra(start, graph)
for i in range(1, node + 1):
    if distance[i] == 100000001: print("INF")
    else: print(distance[i])

 

이 문제는 전형적인 dijkstra 문제였다. dijkstra 원리만 이해한다면 코드 짜는데에는 무리가 없다. 나는 최소힙을 사용하여 문제를 해결하였다.

 

느낀점 : 최댓값 초기화라도, 코드 한줄이라도 신경써서 정성들여 짜자.