[백준 알고리즘] 30974번: What's your ETA? (Python)

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

30974번: What's your ETA?

 

소스코드

import sys
import heapq as hq
import math
input = sys.stdin.readline

def dijkstra(start):
  q = []
  min_dis = [float('inf') for _ in range(n+1)]
  min_dis[start] = 0
  hq.heappush(q, (0, start))

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if prime[arr[cur_node]+arr[next_node]]:
        if min_dis[next_node] > cur_dis + next_dis:
          min_dis[next_node] = cur_dis + next_dis
          hq.heappush(q,(next_dis+cur_dis,next_node))
        
  return min_dis[n]

n,m = map(int,input().split())
arr = [0] + list(map(int,input().split()))
graph = [[] for _ in range(n+1)]
prime = [True for _ in range(10**7+1)]
        
for _ in range(m):
  u,v,w = map(int,input().split())
  graph[u].append((v,w))
  graph[v].append((u,w))
  
for i in range(2,int(math.sqrt(10**7+1))+1):
    if prime[i]:
        j = 2
        while i*j <= 10**7:
            prime[i*j] = False
            j += 1
    
k = dijkstra(1)
if k == float('inf'):
  print('Now where are you?')
else:
  print(k)

 

풀이

★ 문제 자체는 기본적인 다익스트라 + 소수 판별을 해주면 되는 방식이라 그렇게 어렵지 않다고 생각했지만 시간초과가 발생해서 며칠을 고민했던 문제였습니다 ! 소수 판별도 에라토스테네스 체로 해줬고, 최단 경로도 잘 찾은 거 같은데 왜 틀렸을까요 !! 

 

★ 문제는 큐에 집어 넣는 값을 리스트로 줬기 때문이었습니다. 이전까지는 다익스트라 문제든 다른 문제든 리스트를 자주 사용하였습니다. 그리고 별 문제도 없이 통과했었습니다 ! 하지만 구글링을 해보니 튜플이 리트에 비해 더 적은 메모를 사용하고 속도도 빠르다고 합니다. 

 

★ 결과적으론 자신이 맞다고 생각하는데도 계속해서 시간초과가 뜨는 경우, 리스트를 튜플로 바꾼 뒤 제출하는 방법도 한번 생각해보시면 좋을 거 같습니다 :))