[Algorithm] 미로 탐색 2178.py - BFS

https://www.acmicpc.net/problem/2178

from collections import deque

n, m = map(int, input().split())
data = []

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

for i in range(n):
    data.append(list(map(int, input())))

visited = [[0] * (m + 1) for i in range(n + 1)]

queue = deque([[0,0]])
visited[0][0] = 1
while queue:
    a,b= queue.popleft()
    if (a+1)==n and (b+1)==m:
        print(visited[a][b])
        break
    for i in range(4):
        if n>a + dy[i]>=0 and m>b + dx[i]>=0:
            if data[a + dy[i]][b + dx[i]] == 1 and visited[a + dy[i]][b + dx[i]] == 0:
                queue.append([a + dy[i], b + dx[i]])
                visited[a + dy[i]][b + dx[i]] = visited[a][b]+1

1. 미로에 좌표를 부여해 BFS 탐색
   1 (0,0) 0 1 1 1 1
   1 (0,1) 0 1 0 1 0
   1 (0,2) 0 1 0 1 1
   1 (0,3) 1 1 0 1 1

2. 동서남북탐색

3. 최소한 거리 구하기
   1이있는 칸은 다 구했는데 최소의 칸 수를 어떻게 구해야할까?
   visited[a + dy[i]][b + dx[i]] = visited[a][b]+1
   방문 처리를 그 전 값에 1을 더해서 표시한다.
   너비탐색으로 같은 너비에 잇는 값은 같은 방문값을 가지므르 결과값은 최소의 값이 된다.