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

접근 방법 : BFS, 3차원 배열
처음엔 완전탐색인 것 같아서 deepcopy하고 난리를 쳤는데 역시나 시간 초과..
벽 부수는 횟수를 배열로 추가하는 건 생각도 못했다..

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

board = []

for i in range(N):
    board.append(list(sys.stdin.readline().strip()))

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

def bfs(x, y):

    dist = [[[0] * M for _ in range(N)] for _ in range(2)]
    dist[1][0][0] = 1

    que = deque([])
    que.append([0, 0, 1])


    while que:
        x, y, w = que.popleft()

        if x == N - 1 and y == M - 1:
            return dist[w][x][y]

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

            if 0 <= nx < N and 0 <= ny < M:
                if board[nx][ny] == '0' and dist[w][nx][ny] == 0:
                    dist[w][nx][ny] = dist[w][x][y] + 1
                    que.append([nx, ny, w])
                elif board[nx][ny] == '1' and w == 1:
                    dist[0][nx][ny] = dist[w][x][y] + 1
                    que.append([nx, ny, 0])

    return -1

print(bfs(0, 0))