[BOJ][Python]1753 풀이

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

1753번: 최단경로

import heapq
import sys
ssr = sys.stdin.readline

INF = 3000001

def dijkstra(start):
    h = [(0, start)]
    dist[start] = 0
    while h:
        cur_dist, cur_node = heapq.heappop(h)
        if cur_dist > dist[cur_node]:
            continue
        for next_dist, next_node in routes[cur_node]:
            if dist[cur_node]+next_dist < dist[next_node]:
                dist[next_node] = dist[cur_node]+next_dist
                heapq.heappush(h, (dist[next_node], next_node))

v, e = map(int, ssr().split())
k = int(ssr())
routes = [[] for _ in range(v+1)]
dist = [INF for _ in range(v+1)]
for _ in range(e):
    a, b, c = map(int, ssr().split())
    routes[a].append((c, b))
dijkstra(k)
for i in range(1, v+1):
    print(dist[i] if dist[i] != INF else 'INF')

좀 바보같은 실수가 두가지 있어서 가져와봤습니다. 기존에 데이크스트라 풀이랍시고 올려놓은 코드를 보니까 죄다 방문처리를 하고 있더라구요. 운이 좋아서 틀리진 않았습니다만, 데이크스트라는 방문처리를 했을 때 에러가 날 가능성이 있습니다. 좀 더 정확하게 말하자면 제가 기존에 작성했던 코드는 이미 처리를 한 노드인지 확인을 하는 코드가 있으면서도 방문처리를 또 하고 있었기 때문에 불필요해서 삭제를 해주었습니다. 만약 이 과정이 없고 dfs/bfs처럼 방문처리를 할 경우 문제가 일어날 가능성이 있습니다. 나중에 발견되는 경로가 사실 훨씬 작은 가중치합을 갖고 있을 수 있지만 이미 방문한 노드일 경우 연산을 하지 않으니 결과에 오류가 생길 수 있겠죠.

 

그리고 이 문제의 경우 노드의 가중치는 최대 10이라는 말을 착각해서 INF를 11로 초기화하는 실수를 할 수 있습니다(저도 그랬구요). 최대 간선이 30,000개이므로 최대 간선이 주어지고 모든 가중치가 1일 경우 10번 이상 노드를 거치는 경로일 경우 제대로 된 결과는 10을 넘는 값이어야겠지만 초기화를 11로 해놔서 알고리즘 특성상 11을 넘는 값이 배열에 갱신이 될 리가 없습니다. 어떻게 보면 함정에 보기 좋게 당한거죠. 그래서 배열을 초기화할 때 INF의 값을 최대 10의 가중치 * 최대 간선의 갯수 30,000 보다 큰 값을 넣어서 초기화해주면 문제없이 작동할 겁니다.

 

아직 데이크스트라를 마음대로 주무르는 느낌이 아니라서 한동안은 데이크스트라 문제 풀이를 진행할지도 모르겠습니다.

 

추가//

데이크스트라에 대해 정리한 글을 업로드했습니다. 데이크스트라가 좀 더 궁금하신 분들은 읽어보시면 좋을 것 같아요.

https://justduke.tistory.com/356

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드