풀이

벽부수고 이동하기 -1 에서 부술 수 있는 벽의 개수만 지정해주면 금방 풀 수 있는 문제.
배운점
1) visited함수의 3차원 선언
2) 리스트 sys선언

from collections import deque
import sys
n, m ,k = map(int, sys.stdin.readline().split())
array = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0,0,-1,1]
# 3차원 리스트 (행, 열, 벽을 깬 여부) 생성
visited = [[[0] * (k+1) for _ in range(m)] for _ in range(n)]

def solve(x,y,wall_break_left, visited, array):
    q = deque()
    q.append((x,y,wall_break_left))
    visited[x][y][wall_break_left] = 1

    while q:
        x,y,wall_break_left = q.popleft()
        if wall_break_left < 0:
            continue
        if x == n-1 and y == m-1:
            return visited[x][y][wall_break_left]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= n or ny<0 or ny>=m:
                continue
            # 벽을 깨지 않고 이동
            if array[nx][ny] == 0 and visited[nx][ny][wall_break_left] == 0:
                q.append((nx,ny, wall_break_left))
                visited[nx][ny][wall_break_left] = visited[x][y][wall_break_left] + 1
            # 벽을 깨고 이동
            if array[nx][ny] == 1 and wall_break_left > 0 and visited[nx][ny][wall_break_left - 1] == 0:
                q.append((nx,ny, wall_break_left-1))
                visited[nx][ny][wall_break_left-1] = visited[x][y][wall_break_left] +1
    return -1

print(solve(0,0, k,visited,array))