[백준 9376번] 탈옥 (Python3)

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

def check(y,x):
  MIN = [1e5]*3
  for i in range(4):    
    y1,x1 = y+dy[i],x+dx[i]
    if N>y1>=0 and M>x1>=0:
      for n in range(3):
        MIN[n] = min(MIN[n],visited[n][y1][x1])
  return sum(MIN)

def BFS(y,x):
  visited = [[1e5]*M for i in range(N)]
  dq = collections.deque([(y,x,0)])
  while dq:
    y,x,c = dq.popleft()
    if visited[y][x]<=c:
      continue
    visited[y][x] = c
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if board[y1][x1]==1:
          continue
        if board[y1][x1]<0:
          dq.append((y1,x1,c+1))
        else:
          dq.appendleft((y1,x1,c))
  return visited

for _ in range(int(input())):
  N,M = map(lambda x:int(x)+2,input().split())
  
  board = [[0]*M]+[[0,*map(lambda x:int(x=="$")*2-int(x=="#")+int(x=="*"),input().strip()),0] for i in range(N-2)] + [[0]*M]
  
  start = []
  for y in range(N):
    for x in range(M):
      if board[y][x]==2:
        start.append((y,x))
        
  visited = [BFS(0,0),BFS(*start[0]),BFS(*start[1])]
  
  result = 1e5; door = 0
  for y in range(N):
    for x in range(M):
      if board[y][x]<0:
        door = 1
        result = min(result,check(y,x)+1)
  print(min(result,check(0,0)))

0-1 BFS로 해결하였다.

죄수가 두명이라는 점이 약간 까다로웠다.

 

풀이를 설명하면,

1. board의 바깥쪽을 0으로 감싼다. (탈출을 처리하기 쉽게하기 위해서)

2. BFS를 감옥 밖(0,0) 에서 한번, 두 죄수의 위치에서 한번씩, 총 3번 돌린다.

3. BFS는 문을 만나면 c를 +1 하는 방식으로 0-1 BFS를 하고, 각 지점에 도착할때의 문의 개수의 최솟값을 visited에 기록한다.

4. 모든 문에 대해서 check를 실행한다. check는 현재 위치에서 상하좌우에 대해 위에서 저장한 3개의 visited 배열의 최솟값의 합을 출력한다.

5. (모든 문에서 실행한 check의 값+1)과 (0,0에서 실행한 check 값) 중 더 작은 값을 출력한다.

 

즉, 쉽게 말하면 각 문에 대해서 문에서부터 "밖까지의 거리+죄수1까지의 거리+죄수2까지의 거리" 의 최솟값을 구하는 것이다. (여기서 거리는 지나가는 문의 개수) 이때, 문을 하나도 거치지 않고도 탈출하는 경우가 존재할 수 있으므로 0,0에서도 실행해주어야한다.

 

 

오늘의 교훈) 0-1 BFS는 유용하다.