벽 부수고 이동하기 2

1. 개요

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

2. BFS 풀이

from collections import deque
from sys import stdin

def solution():
    q = deque()
    input = stdin.readline

    N, M, K = map(int, input().split())
    D = [[[0]*(K+1) for _ in range(M)] for _ in range(N)]
    G = [list(map(int,input().strip())) for _ in range(N)]
    dx, dy = [1,0,-1,0], [0,1,0,-1]

    def bfs():
        q.append([0,0,K])
        D[0][0][K] = 1
        
        while q :
            x, y, z = q.popleft()

            if x==N-1 and y==M-1:
                return D[x][y][z]

            for i in range(4):
                nx, ny = dx[i]+x, dy[i]+y

                if not (0<=nx<N and 0<=ny<M):
                    continue
                    
                if G[nx][ny] and z>0 and D[nx][ny][z-1]==0:
                    D[nx][ny][z-1] = D[x][y][z]+1
                    q.append([nx,ny,z-1])

                elif not G[nx][ny] and D[nx][ny][z]==0:
                    D[nx][ny][z] = D[x][y][z]+1
                    q.append([nx,ny,z]) 
        return -1

    return bfs()

print(solution())