[백준] 17368 백도어 - python

문제 링크
https://www.acmicpc.net/problem/17396

시도 1. 시간초과

n, m = map(int, input().split())
INF = int(1e9)

canSee = list(map(int, input().split()))

graph = [[] for _ in range(n)]
visited = [False] * (n)
distance = [INF] * (n)

for _ in range(m):
  a, b, t = map(int, input().split())
  if (canSee[a] == 0 or a == n-1) and (canSee[b] == 0 or b == n-1):
    graph[a].append((b, t))
    graph[b].append((a, t))
  
def get_smallest_node():
  min_value = INF
  index = 0
  for i in range(n):
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i 
  return index

def dijkstra(start):
  distance[start] = 0
  visited[start] = True
  for v in graph[start]:
    distance[v[0]] = v[1]
  
  for _ in range(n - 1):
    now = get_smallest_node()
    visited[now] = True
    for j in graph[now]:
      cost = distance[now] + j[1]
      if cost < distance[j[0]]:
        distance[j[0]] = cost
        
dijkstra(0)

if distance[-1] == INF:
  print(-1)
else:
  print(distance[-1])

• 구현 방법 : 다익스트라 알고리즘 - 선형 탐색
• 시간 복잡도 : O(n²)

시도2. 시간초과

import heapq
n, m = map(int, input().split())
INF = int(1e9)

canSee = list(map(int, input().split()))

graph = [[] for _ in range(n)]
distance = [INF] * (n)

for _ in range(m):
  a, b, t = map(int, input().split())
  if (canSee[a] == 0 or a == n-1) and (canSee[b] == 0 or b == n-1):
    graph[a].append((b, t))
    graph[b].append((a, t))

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
        
dijkstra(0)

if distance[-1] == INF:
  print(-1)
else:
  print(distance[-1])

• 구현 방법 : 다익스트라 알고리즘 - 우선순위 큐
• 시간복잡도 : O(nlogn)
• 실패 원인 : 인풋을 받는 코드에서 sys.stdin.readline() 을 사용하지 않았다

시도3. 성공

import heapq
import sys
input = sys.stdin.readline
inf = sys.maxsize

n, m = map(int, input().split())
canSee = list(map(int, input().split()))
canSee[-1] = 0

graph = [[] for _ in range(n)]

for _ in range(m):
  a, b, t = map(int, input().split())
  graph[a].append((b, t))
  graph[b].append((a, t))

q = []
heapq.heappush(q, (0, 0))
distance = [inf] * n
distance[0] = 0
while q:
  dist, now = heapq.heappop(q)
  if distance[now] < dist:
    continue
  for nxt, nxt_cost in graph[now]:
    cost = dist + nxt_cost
    if cost < distance[nxt] and canSee[nxt] == 0:
      distance[nxt] = cost
      heapq.heappush(q, (cost, nxt))

print(distance[-1] if distance[-1]<inf else -1)

• 접근방법 : 다익스트라 알고리즘 - 우선순위 큐
• 시간복잡도 : O(nlogn)

배운점

1. 다익스트라 알고리즘 사용법
2. 여러줄의 입력을 받을 때에는 반드시 sys.stdin.readlind() 을 사용하자. 메모리와 실행시간을 절약한다.
3. list보다 tuple이 iteration을 도는 속도가 더 빠르다. 따라서 원소를 수정할 일이 없는 경우는 tuple을 사용하자.