2178: 미로 탐색

import sys
from collections import deque

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

def bfs(x, y):
    queue = deque([]); queue.append([0, 0])

    while queue:
        x, y = map(int, queue.popleft())
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            if Map[nx][ny] == 1:
                Map[nx][ny] = Map[x][y] + 1
                queue.append([nx, ny])
    return Map[N-1][M-1]

N, M = map(int, sys.stdin.readline()[:-1].split(' '))
Map = []
for _ in range(N):
    tmp = list(map(int, sys.stdin.readline()[:-1]))
    Map.append(tmp)

print(bfs(0, 0))

• [0, 0]부터 시작하여, bfs순회를 하면서 Map의 값이 1인 경우에 상하좌우 탐색
• nx = x + dx[i]; ny = y + dy[i]는 new x, y 좌표
• queue에 nx, ny 좌표를 넣어주고, Map[nx][ny]에 이전 depth의 Map값 (Map[x][y]) + 1을 할당해줌
• Map[-1][-1]값이 지나야 하는 최소의 칸 수가 된다