[Ch.5 - DFS/BFS] 미로 탈출

My code

from collections import deque

n,m = map(int,input().split())

miro = []
for i in range(n):
    miro.append(list(map(int,input().split())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

print(bfs(0,0))

Code Review

이번 문제는 미로에서 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하는 문제였습니다. 미로의 시작 지점에서 가까운 노드부터 차례대로 탐색하기 위해 BFS 를 이용했습니다. BFS 를 이용하여 노드를 탐색해나가며 현재 위치에서 상, 하, 좌, 우로의 위치를 확인하여 만약 해당 노드를 처음 방문하는 경우 이전 노드의 값에 1을 더하여 이동 거리를 기록해주었습니다. 이 과정을 Queue 가 빌 때까지 반복하면 최종 출구 위치까지 이동한 거리를 return 하여 출력할 수 있습니다.