[Python] 미로 탐색 - 백준 (BFS)

해당 글은 백준 2178번 문제 '미로 탐색'을 다룬다.

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

설명

BFS로 이동할 수 있으면 +1 씩 더해서 총 이동거리를 계산하였다.

그리고 마지막 행렬의 [n-1][m-1] 인덱스의 값이 최소 이동 칸 수 이다.

 

코드

from collections import deque

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 and nx < n and ny >= 0 and ny < m:
                if data[nx][ny] == 1:
                    q.append((nx, ny))
                    data[nx][ny] = data[x][y] + 1
    return data[n-1][m-1]


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

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

print(bfs(0, 0))