[백준 3860번] 할로윈 묘지 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def BFS(e):
  visited = [[0]*M for i in range(N)]
  y,x,t = hole[e]
  dq = deque([(y,x,0)])
  while dq:
    y,x,d = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if board[y][x]:
      graph.append((e,board[y][x],d+t))
      continue
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and not visited[y1][x1] and board[y1][x1]!=-1:
        dq.append((y1,x1,d+1))

def BF():
  for i in range(E+2):
    for now,next,w in graph:
      if DP[now] == 1e9:
        continue
      if DP[next] > DP[now]+w:
        DP[next] = DP[now]+w
        if i == E+1:
          return True

while 1:
  M,N = map(int,input().split())
  if not N:
    break
  
  board = [[0]*M for i in range(N)]
  G = int(input())
  for _ in range(G):
    x,y = map(int,input().split())
    board[y][x] = -1
  
  E = int(input())
  hole = {}
  hole[0] = (0,0,0)
  hole[E+1] = (N-1,M-1,0)
  for i in range(1,E+1):
    x1,y1,x2,y2,t = map(int,input().split())
    board[y1][x1] = i
    hole[i] = (y2,x2,t)
  board[N-1][M-1] = E+1
  
  graph = []
  for e in range(E+1):
    BFS(e)
  DP = [1e9]*(E+2)
  DP[0] = 0
  if BF():
    print("Never")
  else:
    if DP[E+1] == 1e9:
      print("Impossible")
    else:
      print(DP[E+1])

벨만포드 문제이다.

 

문제를 이해하기 어려울 수 있는 문제이다. 설명이 확실하지 않고 애매한 부분이 많아 까다롭다.

오민식의 고민 [백준 1219번] 오민식의 고민 (Python3) (tistory.com) 문제를 풀어봐서 오히려 더 헷갈렸던게, 오민식의 고민 문제에서는 사이클이 있는데 도착할 수 없는 경우와 사이클이 있는데 도착할 수 있는 경우를 구분해주었어야 했다. 그러나 이 문제는 그럴 필요 없이 사이클이 존재하면 무조건 Never를 출력하면 된다.

 

알고리즘은 간단하다.

1. 출발지점과 모든 귀신구멍에서 BFS를 실행하여 각 지점에서 귀신구멍과 도착지점까지의 거리에 대한 그래프를 그린다.

2. 그래프를 바탕으로 벨만 포드 알고리즘을 이용하여 음의 사이클을 판별한다.

3. 결과값을 출력한다.

 

이때, BFS를 하는 과정에서 조심해야할 점이 귀신구멍에 도착하면 바로 continue를 해주어야 한다. 귀신구멍에서는 무조건 구멍으로 들어가야지, 상하좌우로 이동할 수 없기 때문이다.

 

 

오늘의 교훈) 문제를 정확하게 읽자