[백준] 17396번 백도어 파이썬 코드

코드

import sys, heapq # 다익스트라 알고리즘은 heap 자료구조를 이용

input = sys.stdin.readline
INF = 100000 * 100000 + 1
# INF의 크기, 987654321로 잡았을 때는 틀렸다.
# 이 값을 어떻게 구할지 생각해봐야겠다.

n,m = map(int, input().split())
junctions = [*map(int, input().split())] # 분기점
graph = [[] for _ in range(n)] # 양방향 그래프
visited = [INF]*n # 가중치가 양수라서 다익스트라 알고리즘 사용가능

for _ in range(m):
  a,b,t = map(int,input().split())
  graph[a].append((b,t))
  graph[b].append((a,t))
  
def dijkstra():
  queue = [(0,0)] # 첫 시작점은 0으로 고정
  visited[0] = 0 # 시작점의 이동 값은 0
  while queue:
    now, next = heapq.heappop(queue) # 이동거리가 최소인 것을 꺼내준다.
    if now > visited[next]: continue # 시간 초과 방지
    for i in graph[next]:
      cost = now+i[1] # 원래 값 + 다음으로 넘어갈 때의 비용
      if visited[i[0]] > cost and (i[0] == n-1 or not junctions[i[0]]):
      # 최단거리 갱신할 수 있고 n-1번째 분기점이거나 분기점의 값이 0일 때
        visited[i[0]] = cost # 최단거리 갱신
        heapq.heappush(queue,(visited[i[0]],i[0])) #힙에 값을 넣어준다.

dijkstra()
print(visited[n-1]) if visited[n-1] != INF else print(-1)

전형적인 다익스트라 알고리즘 문제이지만, 오랜만에 풀어서 조금 헤맸다. 한 번에 많이 푸는 것도 도움이 되지만 꾸준히 풀어나가는 것 또한 중요하다는 것을 깨달았다.

 

다익스트라 알고리즘을 효율적으로 구현하기 위해서는 heap 자료구조를 사용할 수 있으며, 파이썬에서는 heapq모듈을 이용하면 된다. 참고로 파이썬에서의 힙은 최소힙이다.

 

틀렸던 이유는 2가지였다. 첫째로 시간초과, 다음으로는 INF의 값을 충분히 크게 잡아주지 않았다는 점이다.

 

시간초과의 경우에는 다음 한 줄을 추가하면 해결할 수 있다.

if now > visited[next]: continue

방문 기록에 저장된 정점 next의 최소비용보다 다른 정점을 거쳐서 i까지 도달한 누적비용이 더 크면  탐색할 필요가 없는 값이기 때문에 그냥 넘겨서 시간을 절약할 수 있다. 누적비용이 더 큰 상태에서 연결된 간선을 통해 다른 정점을 탐색하더라도 비용이 더 작은 경우는 없기 때문이다.

 

다음으로 INF의 값이 문제가 됐다. 습관적으로 987654321로 주었는데 이게 발목을 잡을 줄은 몰랐다. 질문 게시판에 100000 * 100000 + 1 이상으로 잡아야 에러가 나지 않는다고 글을 올려주셔서 해결했다. 아마 정점의 개수^2 + 1 을 해주어야 하는 것 같다. 이제 깨달았으니 문제 조건을 꼼꼼히 읽고 주의 깊게 문제 풀이를 해야겠다.

 

참고

https://www.acmicpc.net/board/view/98412

글 읽기 - 혹시 68%쯤에서 에러가 나시는 분들께 드리는 문제 조언입니다.