[백준 16933번] 벽 부수고 이동하기 3 (Python3)

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

N,M,K = map(int,input().split())

def BFS():
  dq = deque()
  dq.append((0,0,0,1))
  visited = [[[0]*M for i in range(N)] for i in range(K+1)]
  while dq:
    y,x,k,cnt = dq.popleft()
    if visited[k][y][x]:
      continue
    if y == N-1 and x == M-1:
      return cnt
    if board[y][x] == 1 and cnt%2 == 1:			#현재 벽인데 밤일 경우
      dq.append((y,x,k,cnt+1))
      continue
    visited[k][y][x] = 1
    
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        if board[y][x] == 0:
          if visited[k][y1][x1]:
            continue
          dq.append((y1,x1,k,cnt+1))
        else:
          if k == K:
            continue
          if visited[k+1][y1][x1]:
            continue
          dq.append((y1,x1,k+1,cnt+1))
  return -1

board = []
for i in range(N):
  board.append([*map(int,[*input().strip()])])

print(BFS())

 

전형적인 BFS 문제로 간단하게 해결할 수 있다.

요약하면

1. dq에는 xy 좌표, 부순 벽 개수, 이동거리를 기록, 4방향 BFS 실행

2. 벽으로 이동할 경우 visited를 다른 층에 기록, 벽 부순 개수가 K개면 continue

3. 현 위치가 벽이면서 현재 밤일 경우 이동거리를 1 늘린 후 다시 dq에 넣음

4. N-1,M-1에 도착하면 이동거리 출력

 

3차원 visited list를 이용하는건 다른 벽 부수기 문제에서 풀어봤기에 익숙하고 현 위치가 밤인 경우만 주의하면 되기 때문에 어렵지 않은 문제

 

오늘의 교훈) 3차원 visited list를 잘 활용하자