[Graph] 미로 탐색

from collections import deque

n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]

q = deque()
q.append((0, 0))

direction = {0: (0, 1), 1: (0, -1), 2: (1, 0), 3: (-1, 0)}
    
while(q):
    x, y = q.popleft()
        
    for i in range(4):
        x2, y2 = x + direction[i][0], y + direction[i][1]
        if x2>=0 and x2<n and y2>=0 and y2<m and maze[x2][y2]==1:
            q.append((x2, y2))
            maze[x2][y2] = maze[x][y] + 1
    
print(maze[n-1][m-1])

연결된 경로 표현은 2차원 배열
최소 칸 수를 구하는 문제 -> BFS 활용
전에 풀었던 방문 길이 문제를 참고하여 위쪽 아래쪽 오른쪽 왼쪽 방향으로 이동하는 경우를 계산
주어진 미로의 범위를 넘어가지 않도록 체크하면서 이동할 수 있는 칸이면 해당 칸의 값을 원래 있던 칸의 값에 1을 더하는 방식으로 카운트해 최종 도착 칸에는 이동한 칸 수가 저장