[2178] 미로 탐색

bfs문제

1.시작점(1,1)에서 (N,M)까지 최소칸수구하기 ( 시작칸 도착칸 포함!)

2.1로 표시된곳만 갈 수 있음

 

 

def bfs(i,j):
    while queue:
        i,j = queue.pop(0)
        if i == N-1 and j == M-1:  #(도착점오면 출력)
            return visited[i][j]
        for d in range(4):
            ni = i + di[d]
            nj = j + dj[d]
            if 0<= ni < N and 0<= nj <M and miro[ni][nj] and visited[ni][nj] == 0:
                queue.append((ni,nj))
                visited[ni][nj] = visited[i][j] + 1


di = [-1,0,1,0]
dj = [0,1,0,-1]
N,M = map(int,input().split())
miro = [list(map(int,input())) for _ in range(N)]
visited = [[0]* M for _ in range(N)]
queue = [(0,0)]
visited[0][0] = 1
print(bfs(0,0)) # 시작점 (1,1)이니까 (0,0)