백준 - 미로 탐색 (BFS)

백준 미로 탐색

해결 과정

• 처음에는 DFS를 활용해야하는 문제인줄 알았다.
• 하지만 BFS를 활용하는 문제!

BFS 해결

• https://ansanghyun20.github.io/algorithm/2021/12/03/DFS-BFS.html
• BFS를 사용해 1이 발견 될때매다 자신의 값+1 을 하며 채워나간다.
• 상하좌우 순으로 동작.

from collections import deque

N, M = map(int, input().split())
lst = []
for i in range(N):
    lst.append(list(map(int,str(input()))))

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = []
queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.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 or lst[nx][ny]==0 :
            continue
        # 1을 만났을 경우
        if lst[nx][ny] == 1:
            # 1을 만난 친구에게 -> 나의 값 +1
            lst[nx][ny] = lst[x][y] +1
            # 새로 만난 친구의 좌표를 queue에 저장
            queue.append((nx, ny))

print(lst[N-1][M-1])