[백준] 미로 탐색.py

from collections import deque
N, M = map(int, input().split())
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
dist = [[0 for _ in range(M)] for _ in range(N)]
maps = [list(map(int, list(input()))) for _ in range(N)]
queue = deque()
queue.append((0,0))
dist[0][0] = 1
while queue:
    cur_y, cur_x = queue.popleft()
    maps[cur_y][cur_x] = 0
    for i in range(4):
        nxt_y, nxt_x = cur_y + dirs[i][0], cur_x + dirs[i][1]
        if 0 <= nxt_y < len(maps) and 0 <= nxt_x < len(maps[0]) and maps[nxt_y][nxt_x] == 1:
            queue.append((nxt_y, nxt_x))
            dist[nxt_y][nxt_x] = dist[cur_y][cur_x] + 1
            maps[nxt_y][nxt_x] = 0

print(dist[N-1][M-1])