Baekjoon Training #2178

---

#2178 미로 탐색

#deque class를 collections module에서 import
from collections import deque

N, M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]

def bfs(maze, start):
    queue = deque([start])
    #행의 개수 (세로 길이)
    n = len(maze)
    #열의 개수 (가로 길이)
    m = len(maze[0])
    #전체 좌표의 distances값을 -1 default값으로 설정
    distances = [[-1 for _ in range(m)] for _ in range(n)]
    distances[start[0]][start[1]] = 1

    while queue:
        #이전에 다룬 위치를 x,y로 설정하고 queue에서 꺼내줌
        x, y = queue.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            #새로운 위치인 new_x와 new_y를 이용하여 조사
            new_x, new_y = x + dx, y + dy
            #maze 내부이고 지나갈 수 있는 길(maze == 1)이고 지정된 위치이고 지나간적 없는 길(distances == -1)
            if (0 <= new_x < n) and (0 <= new_y < m) and (maze[new_x][new_y] == 1) and (distances[new_x][new_y] == -1):
                #해당위치의 distances의 크기를 이전 위치 보다 1 큰값으로 설정
                distances[new_x][new_y] = distances[x][y] + 1
                #queue에 해당 위치 좌표를 대입
                queue.append((new_x, new_y))
    #n,m위치의 distances값을 return, index여서 0부터 시작하므로 1씩 빼줌
    return distances[n-1][m-1]

print(bfs(maze, (0, 0)))

BFS로 풀이를 진행하였다. 우선 deque을 import하고 가로 길이, 세로 길이를 입력받아주고 maze라는 2차원 배열을 만들어주고 bfs함수를 만들었다. bfs함수에서는 상하좌우를 확인하는 스위치를 만들어두고 계속해서 사방을 조사하면서 한칸씩넘어갈때마다 distances를 1씩 증가시켜주며 이동 거리를 결정해주었다. 각 위치에 도달하는 이동 거리를 정해주다보면 원하는 최종위치까지의 이동거리도 자연스럽게 찾을 수 있게된다.

---