백준 2206 - 벽 부수고 이동하기 (파이썬)

Answer

from sys import stdin
from collections import deque

input = stdin.readline

def bfs():
    global matrix
    queue = deque([(0, 0, 0)])
    visited = [[[0] * 2 for _ in range(M)] for __ in range(N)]
    visited[0][0][0] = 1

    while queue:
        x, y, z = queue.popleft()

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

        for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
            nx = dx + x
            ny = dy + y

            if 0 <= nx < N and 0 <= ny < M:
                if matrix[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append((nx, ny, 1))
                elif matrix[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append((nx, ny, z))

    return -1

N, M = map(int, input().split())
matrix = [list(map(int, input().replace('\n', ''))) for _ in range(N)]
print(bfs())