BOJ - 14442 - 벽 부수고 이동하기 2

import sys
from collections import deque

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

def BFS(maps, N, M, K):
    visit = [[[0 for _ in range(K+1)] for _ in range(M)] for _ in range(N)]
    visit[0][0][0] = 1
    Q = deque()
    Q.append((0, 0, 0))

    while Q:
        x, y, w = Q.popleft()
        if x == N-1 and y == M-1:
            return visit[x][y][w]

        for i in range(4):
            nx, ny, nw = x+dx[i], y+dy[i], w+1
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny][w]:
                    if maps[nx][ny] == '0':
                        visit[nx][ny][w] = visit[x][y][w] + 1
                        Q.append((nx, ny, w))
                    if maps[nx][ny] == '1':
                        if nw <= K:
                            visit[nx][ny][nw] = visit[x][y][w] + 1
                            Q.append((nx, ny, nw))

    return -1

def solution():
    N, M, K = map(int, sys.stdin.readline().split())
    maps = []
    for _ in range(N):
        maps.append(list(map(str, list(sys.stdin.readline().strip()))))

    print(BFS(maps, N, M, K))

solution()

https://www.acmicpc.net/problem/14442