백준 14442 벽 부수고 이동하기 2

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m, k = map(int, input().split())
g = [list(map(int, input())) for _ in range(n)]

check = [[[-1] * (k+1) for _ in range(m)] for _  in range(n)]


q = deque()
q.append((0, 0, 0))
check[0][0][0] = 1
while q:
    x, y, w = q.popleft()
    for d in range(4):
        nx, ny = x +dx[d], y + dy[d]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if g[nx][ny] == 0 and w <= k and check[nx][ny][w] == -1:
            check[nx][ny][w] = check[x][y][w] + 1
            q.append((nx, ny, w))
        if g[nx][ny] == 1 and w < k and check[nx][ny][w+1] == -1:
            check[nx][ny][w+1] = check[x][y][w] + 1
            q.append((nx, ny, w+1))

ans = n*m+1
for i in range(k+1):
    if check[n-1][m-1][i] != -1:
        ans = min(ans, check[n-1][m-1][i])

if ans == n*m+1:
    print(-1)
else:
    print(ans)

(pypy 제출) 부수는 벽의 갯수를 check 배열에 넣었다
시간 줄일 수 있을까?