백준 / 2178 / 미로탐색 (bfs)

from collections import deque

direction = [[1,0], [-1,0], [0,1], [0,-1]]

n, m = [int(v) for v in input().split()]
maps = [[0] * m for _ in range(n)]

for i in range(n):
    maps[i] = list(map(int, input()))

q = deque([[0,0,0]])
result = 0
while q:
    x, y, deph = list(q.popleft())
    if x == n-1 and y == m-1:
        result = deph + 1
        break
    maps[x][y] = 0
    for d in direction:
        nx, ny = x+d[0], y+d[1]
        if 0 <= nx < n and 0<= ny < m and maps[nx][ny]==1:
            maps[nx][ny] = 0
            q.append([nx,ny, deph+1])

print(result)

bfs를 진행하면서 1인 값을 찾은 후 해당 좌표 방문하고 방문한 좌표는 0으로 바꿔서 다시 방문하지 않게 한다. 방문 할때마다 deph +1을 해줘서 마지막 좌표에 도달하면 deph의 크기가 정답이다.