미로 탈출

💻 입력 조건

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸 과 마지막 칸은 항상 1 이다.

💻 출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력 한다.

💻 입력 예시

5 6
101010
111111
000001
111111
111111

💻 출력 예시

10

📖 문제 해결
bfs를 이용하여 차근차근 주위의 좌표들로 이동해가며 해당 좌표로의 최단 경로의 거리를 계산하는 방법을 이용하여 문제를 해결하였습니다. 탐색하고자 하는 좌표(큐에서 popleft()로 빠져나온 좌표)의 상하좌우의 좌표들 중 좌표값이 1인 좌표들을 큐에 넣고 좌표값을 해당 좌표로의 최단 경로의 거리로 업데이트해줍니다. 여기서 해당 좌표로의 최단 경로의 거리는 popleft()로 빠져나온 좌표, 즉 상하좌우로 이동 전 좌표의 좌표값 + 1이 됩니다.(그 좌표에서 1만큼만 움직였기 때문입니다.) 이러한 과정을 반복하다가 마지막 좌표에 도착하게 되면 반복문을 중단하고 마지막 좌표의 좌표값을 반환하는 형식으로 코드를 작성하였습니다.

from collections import deque

# n과 m의 정보 입력 받기
n, m = list(map(int, input().split()))

# 2차원 리스트 정보 입력 받기
graph = []

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

# navigator() 함수는 시작점부터 각 점들의 위치까지의
# 최단 경로의 거리를 계산해주는 함수임

def navigator(graph, x, y):
    
    dx = [-1, +1, 0, 0]
    dy = [0, 0, -1, +1]
    count = 1
    
    queue = deque()
    queue.append((x,y))
    
    # 더이상 빼낼 queue()가 없을 때
    # 즉 도착했을 때 while문 중단
    
    while queue:
        x,y = queue.popleft()
            
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            
            # 알고리즘 상 좌표가 증가하면서 거리를 탐색해야하므로 0이상이어야 하고
            # 인덱스가 범위 내에 있어야 하므로 tx <= n-1 and ty <= m-1 이어야 함
            
            if tx < 0 or ty < 0 or tx > n-1 or ty > m-1:
                continue
            
            # 처음 방문한 노드인 경우(즉, 좌표값이 1인 경우)에만 거리를 계산
            # 그리고 해당 노드를 queue에 추가
            
            if graph[tx][ty] == 1:
                graph[tx][ty] = graph[x][y] + 1
                
                # 끝 노드에 도달한 경우 반복문 중단
                if tx == n-1 and ty == m-1 :
                    break
                    
                queue.append((tx,ty))
    show_graph(graph)

    return graph[-1][-1]