[BFS] 미로 탈출

1. 문제

- (1, 1)에서 시작해서 (N, M)까지 가기 위한 최소의 거리를 구하는 코드

2. 코드 구현

from collections import deque

n, m = map(int,input().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, input())))
    
# 상하좌우
px = [-1, 1, 0, 0]
py = [0, 0, -1, 1]

def dfs(x, y):
    deq = deque()
    deq.append((x, y))
    while deq:
        dx, dy = deq.popleft()
        for i in range(4):
            nx = dx + px[i]
            ny = dy + py[i]
            if nx >= n or nx < 0 or ny >= m or ny < 0:
                continue
            elif maze[nx][ny] == 0:
                continue
            elif maze[nx][ny] == 1:
                maze[nx][ny] = maze[dx][dy] + 1
                deq.append((nx, ny))
    return maze[n-1][m-1]

3. 코멘트

- 구현을 위해 deque 라이브러리 사용 (처음 한번만 호출)
- 큐가 빌 때까지 반복
- 현재 위치에서 네 방향으로의 위치 확인

- 미로 찾기 공간을 벗어난 경우 무시, 벽인 경우 무시
- 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
- 가장 오른쪽 아래 까지의 최단 거리 반환 

- 현재는 '상하좌우' 4면의 경우를 다 구했지만 만약 아래나 오른쪽으로만 이동해야 하는 경우에도 이와 유사하게 코드를 만들 수 있을 것 같다.

- deque를 처음 만들 때, 만약 튜플 형태로 인수를 넣어줘야 된다면 append() 함수를 이용해서 넣어줘야 깔끔하게 들어간다.