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를 잘 활용하자