미로탈출 [bfs]

# 1. 처음 위치는 (1,1) / 미로의 출구는 (n,m)
# 2. 괴물 있는 부분은 0/ 없는 부분은 1
# 3. 탈출하기 위해 움직일 최소 칸의 개수 구하기
# 아이디어 : dfs or bfs -> bfs 같음

from collections import deque
n,m=map(int,input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))

# 이동할 네 방향 설정
dx=[-1,1,0,0]
dy=[0,0,-1,1]

# bfs 소스 코드 구현

def bfs(x,y):
    queue=deque()
    queue.append((x,y))

    while queue:
        x,y=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 graph[nx][ny]==0:
                continue
            if graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                queue.append((nx,ny))
                
    return graph[n-1][m-1]

print(bfs(0,0))

• 최단 거리 구하기 : 대체로 bfs
• 노드를 대각선 방향으로 계산하면서 내려가면 최솟값 구하기 가능
• 방문하지 않은 노드를 큐에 삽입하고, 방문하면 popleft()를 통해 큐에서 꺼낸다. 이 방식으로 모든 노드에 접근 가능.
• 네 방향 탐사는 dx, dy로 한다.