[ 동빈북 ] DFS/BFS - 미로탈출

문제설명

N*M 크기의 미로 (1,1)에서 출발해 괴물을 피하여 (N,M)에 위치한 출구로 탈출한다. 괴물이 없는 부분은 1, 괴물이 있는 부분은 0일때, 출구까지 이동하기 위한 최소 칸의 갯수는? (단, 출발칸과 탈출칸도 모두 포함)

IN
N M
미로의 정보

OUT
최소 이동칸의 개수

문제풀이

from collections import deque

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

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    print(x,y, "->")
    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:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y]+1
                queue.append((nx,ny))
                print(maze[nx][ny], " : " ,nx,ny,"->")
                print(queue)
    #출구까지의 거리 반환
    return maze[n-1][m-1]

print(bfs(0,0))