BFS - 미로 탈출

from collections import deque

n, m = map(int, input().split())
result = 0
graph = []

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

# 상하좌우 이동할 방향 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x, y):
    que = deque()
    #첫 번째 노드를 큐에 넣기
    que.append((x,y))
    #큐가 빌 때까지 실행
    while que:
        #큐의 맨 첫번째 요소를 큐에서 빼서 x, y에 담기
        x,y=que.popleft() 
        for i in range(4):
            #해당 노드의 상하좌우에 노드 존재하는지 살피기
            nx=x+dx[i]
            ny=y+dy[i]
            #범위 벗어나면 무시
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            #1아니고 0이면 무시
            if graph[nx][ny]==0:
                continue
            #1이면 이전 노드의 값에 1 더한 값을 넣어주기
            if graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                #이 노드를 큐에 넣기
                que.append((nx,ny))
        #1인 노드가 더이상 존재하지 않으면, 큐에서 빼기만 하므로 큐가 비게 됨.
    
    return graph[n-1][m-1]

# 맨 위 첫 번째 노드에서 시작해서 이어나가기 때문에
# 0,0 한번만 넣어줌.
print(bfs(0, 0))

풀이 포인트!!

• 0,0 노드에서 시작한다 ⇒ 함수에 0,0만 한번 대입
• while que 돌리기 전에, 초기 위치 노드를 큐에 넣고 시작한다
• while문 안에서, 큐의 첫 번째 요소를 제거하여 현재 위치 노드로 삼는다
• 현재 노드에서 상하좌우 살펴서, 1인 노드에만 "현재노드값+1" 해주고, 이 위치 노드들을 모두 큐에 넣어준다
• 큐가 빌 때까지 위 과정 반복한다
  ⇒ 1인 노드가 더이상 존재하지 않으면, 큐에서 제거되기만 하므로, 큐가 텅 비게 됨.