파이썬(Python)으로 이진 행렬에서 가장 긴 경로 길이 찾기

문제 개요

0은 빈 칸(empty cell), 1은 벽(wall)을 의미하는 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 우리는 첫 번째 행의 임의의 빈 칸에서 출발하여 마지막 행의 임의의 빈 칸에 도달해야 합니다. 이동은 왼쪽, 오른쪽, 아래 세 방향으로만 가능하며, 각 칸은 최대 한 번만 방문할 수 있습니다. 이 조건에서 가능한 가장 긴 경로의 길이를 구하고, 경로가 존재하지 않으면 0을 반환하면 됩니다.

입력 예시

0	0	0	0
0	0	0	1
0	0	0	0

위 행렬의 경우 정답은 10입니다. 예를 들어 다음 순서대로 이동하면 총 10개의 칸을 방문할 수 있습니다.

(0, 3) → (0, 2) → (0, 1) → (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2) → (2, 1) → (2, 0)

풀이 접근: 동적 계획법(DP)

행 단위로 위에서 아래로 진행하면서, 각 행의 각 열에 대해 "그 칸에 도달했을 때 지금까지 방문한 칸 수의 최댓값"을 저장합니다. 같은 행 안에서 왼쪽 방향 전파와 오른쪽 방향 전파를 각각 처리하기 위해 두 개의 보조 배열을 사용합니다.

알고리즘의 단계는 다음과 같습니다.

N := 행렬의 행(row) 개수
M := 행렬의 열(column) 개수
dp := 크기가 M인 리스트, 모든 값을 -1로 초기화
i를 0부터 N-1까지 반복:
- ndp := 크기가 M인 리스트, 모든 값 -1로 초기화
- ndp2 := 크기가 M인 리스트, 모든 값 -1로 초기화
- j를 0부터 M-1까지 반복:
  - matrix[i, j]가 1이 아니고 (i가 0이거나 dp[j] > -1)이면
    - ndp[j] := dp[j] + 1
    - ndp2[j] := dp[j] + 1
- j를 1부터 M-1까지 반복(왼쪽 → 오른쪽 전파):
  - matrix[i, j]가 1이 아니고 ndp[j-1] > -1이면
    - ndp[j] := ndp[j]와 (ndp[j-1] + 1) 중 최댓값
- j를 M-2부터 0까지 1씩 감소시키며 반복(오른쪽 → 왼쪽 전파):
  - matrix[i, j]가 1이 아니고 ndp2[j+1] > -1이면
    - ndp2[j] := ndp2[j]와 (ndp2[j+1] + 1) 중 최댓값
    - ndp[j] := ndp[j]와 ndp2[j] 중 최댓값
- dp := ndp
(dp의 최댓값) + 1을 반환

Python 구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(matrix):
    N = len(matrix)
    M = len(matrix[0])
    dp = [-1 for i in matrix[0]]
    for i in range(N):
        ndp = [-1 for j in matrix[0]]
        ndp2 = [-1 for j in matrix[0]]
        for j in range(M):
            if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
                ndp[j] = dp[j] + 1
                ndp2[j] = dp[j] + 1

        for j in range(1, M):
            if matrix[i][j] != 1 and ndp[j - 1] > -1:
                ndp[j] = max(ndp[j], ndp[j - 1] + 1)

        for j in range(M - 2, -1, -1):
            if matrix[i][j] != 1 and ndp2[j + 1] > -1:
                ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
                ndp[j] = max(ndp[j], ndp2[j])

        dp = ndp
    return max(dp) + 1

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

실행 결과

입력

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