[알고리즘] 미로 탈출

BFS는 간선의 비용이 같을때, 최소 길이를 알 수 있다.

1. 110
   010
   011
2. 120
   010
   011
3. 120
   030
   011
4. 120
   030
   041
5. 120
   030
   045

문제 정의

왼쪽 가장 위에서 오른쪽 가장 아래까지 가는 미로의 경로 중 가장 짧은 경로의 거리를 출력해라.
1이 길, 0이 벽
입력
5 6
101010
111111
000001
111111
111111
출력
10

내 코드

from collections import deque

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

    return graph[n - 1][m - 1]

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

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

#[상, 하, 좌, 우]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(0, 0))