미로 탈출

문제

0은 괴물, 1은 그냥 길 인 맵이 주어졌을 때 (1, 1)에서 (N, M)까지 도착하는 가장 빠른 칸의 개수를 구하시오.

입력

5 6
101010
111111
000001
111111
111111

출력

10

계획

전형적인 BFS로 풀 수 있는 문제 같다.
인접한 노드는 dx, dy를 이용해 4방위를 검사하면 되고
먼저 인덱스를 넘어가면 에러가뜨니 인덱스 범위안인지 먼저 검사한다.
그리고 괴물이 있는 곳인지 확인한다.
통과하면 아직 안가본(== 1)곳인지 확인하고 그 전의 숫자 더하기 1을 다음 갈 곳에 넣고 q에 append한다.

코드

from collections import deque

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


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

def bfs(x, y):
    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny <0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                q.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0, 0))