BFS - 미로 찾기

이코테 p.152 - 미로찾기

N x M 크기의 미로가 있다. (1,1)에서 (N,M)으로 가기위한 최소 이동 칸 수를 구하라.

괴물(0), 길(1)

 

---

BFS를 이용하고..

방문한 노드는 (이전 노드값+1)을 해서 방문표시를 한다.

(N,M)위치의 노드 값을 읽으면 최소 발자취 수가 나온다.

 

from collections import deque

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<0 or nx>=N or ny<0 or ny>=M:
                continue #필드를 벗어나면 다음반복 수행
            if(field[nx][ny]==1):#길일때
                queue.append((nx,ny))
                field[nx][ny]=field[x][y]+1 #발자취 수 기록
    return field[N-1][M-1]



N,M=map(int,input().split())
field=[]
#미로 입력받기
for i in range(N):
    field.append(list(map(int,input())))

print(bfs(0,0))