BOJ - 2206 - 벽 부수고 이동하기

import sys
from collections import deque

def BFS(maps, N, M):

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

    visit = [[[0] * 2 for _ in range(M)] for _ in range(N)]
    visit[0][0][1] = 1
    Q = deque()
    Q.append((0, 0, 1))

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

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

            if 0 <= nx < N and 0 <= ny < M:
                if maps[nx][ny] == 1 and wall == 1:
                    visit[nx][ny][0] = visit[x][y][1] + 1
                    Q.append((nx, ny, 0))
                elif maps[nx][ny] == 0 and visit[nx][ny][wall] == 0:
                    visit[nx][ny][wall] = visit[x][y][wall] + 1
                    Q.append((nx, ny, wall))
    return -1

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

    print(BFS(maps, N, M))

solution()

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