[백준][파이썬] 벽 부수고 이동하기 2

import sys
from collections import deque
n,m,chance = map(int,sys.stdin.readline().split())
map1 =[]
for i in range(n):
    tt = list(sys.stdin.readline())
    map1.append(tt)

dx = [0,0,-1,1]
dy = [1,-1,0,0]
def go(stack):
    while stack:
        x,y,dim = stack.popleft()
        for i in range(4):
            X = x+dx[i]
            Y = y+dy[i]
            if 0<= X < n and 0<=Y<m and map1[X][Y] =="0" and visit[X][Y][dim] == -1:
                visit[X][Y][dim] = visit[x][y][dim] + 1
                stack.append([X,Y,dim])
            if 0<= X <n and 0<= Y <m and map1[X][Y] =="1" and dim < chance and visit[X][Y][dim] == -1:
                visit[X][Y][dim+1] = visit[x][y][dim] + 1 #차원변화도 고려
                stack.append([X,Y,dim+1])
    return

q = deque()
q.append([0,0,0])
visit = [[[-1 for _ in range(chance+1)] for i in range(m)] for k in range(n)]
for i in range(chance+1):
    visit[0][0][i] =1
go(q)
ans = []
for i in range(chance+1):
    if visit[n-1][m-1][i] != -1:
        ans.append(visit[n-1][m-1][i])
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))