Python BFS로 미로 행렬 탈출 최소 이동 횟수 구하기

0은 빈 칸, 1은 벽을 나타내는 이진 행렬(binary matrix)이 주어졌다고 가정해 보겠습니다. 왼쪽 위 모서리인 (0, 0)에서 출발해 오른쪽 아래 모서리인 (R-1, C-1)까지 이동할 때, 거쳐야 하는 최소 칸 수를 구하는 것이 이 문제의 목표입니다. 여기서 R은 행(row)의 개수, C는 열(column)의 개수를 뜻하며, 어떤 경로로도 도달할 수 없는 경우에는 -1을 반환해야 합니다.

예를 들어 입력 행렬이 다음과 같다고 해보겠습니다.

이 경우 정답은 8입니다. 아래와 같은 경로를 따라 이동하면 총 8칸 만에 도착점에 도달할 수 있기 때문입니다.

BFS(너비 우선 탐색)를 활용한 풀이 전략

미로에서 최단 거리를 구하는 문제는 BFS 알고리즘으로 효율적으로 해결할 수 있습니다. BFS는 시작 지점에서 가까운 칸부터 차례대로 탐색하기 때문에, 목적지에 처음 도달했을 때의 이동 거리가 곧 최솟값이 됩니다. 풀이 과정은 다음과 같습니다.

• R := 행의 개수, C := 열의 개수로 설정합니다.
• 큐(q)를 준비하고, matrix[0, 0]이 0이라면 시작 정보 (0, 0, 1)을 넣습니다. 마지막 값 1은 현재까지 이동한 칸 수를 의미합니다.
• 시작 칸을 방문 처리합니다. 즉, matrix[0, 0] := 1로 바꿔 재방문을 막습니다.
• 큐에서 삼중항 (r, c, d)를 하나씩 꺼내며 다음을 반복합니다.
  • (r, c)가 도착점 (R-1, C-1)과 같다면 d를 반환합니다.
  • 상하좌우 네 방향 [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]의 각 좌표 (x, y)에 대해, 좌표가 행렬 범위 안에 있고 해당 칸이 0(빈 칸)이라면 방문 처리한 뒤 (x, y, d+1)을 큐에 추가합니다.
• 큐가 비워질 때까지 도착점에 도달하지 못했다면 -1을 반환합니다.

방문한 칸을 1로 표시하면 벽과 마찬가지로 작동하여 같은 칸을 중복 탐색하는 것을 막을 수 있습니다. 덕분에 각 칸은 최대 한 번만 큐에 들어가며, 전체 시간 복잡도는 O(R×C)로 매우 효율적입니다.

예제 코드

아래 파이썬 구현을 통해 동작 방식을 더 자세히 살펴보겠습니다.

def solve(matrix):
    R, C = len(matrix), len(matrix[0])
    q = [(0, 0, 1)] if not matrix[0][0] else []
    matrix[0][0] = 1
    for r, c, d in q:
        if (r, c) == (R - 1, C - 1):
            return d
        for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= x < R and 0 <= y < C and matrix[x][y] == 0:
                matrix[x][y] = 1
                q.append((x, y, d + 1))
    return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

입력

[
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]

출력

8