파이썬으로 행렬 경로의 음수가 아닌 최대 곱 찾기

m × n 크기의 행렬이 하나 주어져 있다고 가정해 보겠습니다. 시작 지점은 왼쪽 위 모서리 셀인 (0, 0)이며, 매 단계마다 행렬 안에서 오른쪽 또는 아래 방향으로만 이동할 수 있습니다. 이때 왼쪽 위 (0, 0)에서 오른쪽 아래 모서리 (m-1, n-1)까지 이어지는 모든 가능한 경로 가운데, 경로에 놓인 값들의 곱이 음수가 아니면서 최대가 되는 경로를 찾아야 합니다. 만약 결과값이 너무 커진다면, 최대 곱을 10⁹+7로 나눈 나머지를 반환하면 됩니다.

문제 예제

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

이때 출력은 256입니다. 그 이유는 아래와 같이 색칠된 경로를 따라 이동하기 때문입니다.

이 경로의 곱은 [2 * 2 * (-4) * (-8) * 2] = 256이 됩니다.

풀이 접근 방법

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 각 셀에 도달했을 때 만들어질 수 있는 곱의 '최댓값'과 '최솟값'을 쌍(pair)으로 함께 저장하는 것입니다. 음수를 곱하면 부호가 뒤집히기 때문에, 현재까지의 최솟값(절댓값이 큰 음수)이 이후에 오히려 전체 최댓값이 될 수 있기 때문입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• p := 10⁹+7 (모듈러 상수)
• m := 행렬의 행 개수
• n := 행렬의 열 개수
• dp := 입력 행렬과 같은 크기의 2차원 배열, 0으로 초기화
• i를 0부터 m-1까지 반복:
  • j를 0부터 n-1까지 반복:
    • i = 0이고 j = 0이면 → dp[i][j] := (matrix[i][j], matrix[i][j]) 쌍 저장
    • i = 0이면 → ans1 := dp[i][j-1][0] * matrix[i][j], dp[i][j] := (ans1, ans1)
    • j = 0이면 → ans1 := dp[i-1][j][0] * matrix[i][j], dp[i][j] := (ans1, ans1)
    • 그 외의 경우:
      • ans1 := dp[i-1][j][0] * matrix[i][j]
      • ans2 := dp[i-1][j][1] * matrix[i][j]
      • ans3 := dp[i][j-1][0] * matrix[i][j]
      • ans4 := dp[i][j-1][1] * matrix[i][j]
      • maximum := ans1, ans2, ans3, ans4 중 최댓값
      • minimum := ans1, ans2, ans3, ans4 중 최솟값
      • 만약 maximum < 0이면 → dp[i][j] := (minimum, minimum)
      • 만약 minimum > 0이면 → dp[i][j] := (maximum, maximum)
      • 그 외의 경우 → dp[i][j] := (maximum, minimum)
• 마지막으로 dp[m-1][n-1][0] < 0이면 -1을 반환하고, 그렇지 않으면 dp[m-1][n-1][0] % p를 반환

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(matrix):
    p = 1e9+7
    m = len(matrix)
    n = len(matrix[0])

    dp = [[0 for _ in range(n)] for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = [matrix[i][j], matrix[i][j]]

            elif i == 0:
                ans1 = dp[i][j-1][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]

            elif j == 0:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]

            else:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                ans2 = dp[i-1][j][1] * matrix[i][j]
                ans3 = dp[i][j-1][0] * matrix[i][j]
                ans4 = dp[i][j-1][1] * matrix[i][j]
                maximum = max(ans1, ans2, ans3, ans4)
                minimum = min(ans1, ans2, ans3, ans4)
                if maximum < 0:
                    dp[i][j] = [minimum, minimum]
                elif minimum > 0:
                    dp[i][j] = [maximum, maximum]
                else:
                    dp[i][j] = [maximum, minimum]

    if dp[m-1][n-1][0] < 0:
        return -1
    else:
        return int(dp[m-1][n-1][0] % p)

matrix = [[2,-4,2],[2,-4,2],[4,-8,2]]
print(solve(matrix))

입력

[[2,-4,2],[2,-4,2],[4,-8,2]]

출력

256

복잡도 분석

이 알고리즘은 행렬의 모든 셀을 한 번씩만 방문하므로 시간 복잡도는 O(m×n), 각 셀마다 최댓값·최솟값 쌍을 저장하므로 공간 복잡도 역시 O(m×n)입니다. 완전 탐색으로 모든 경로를 확인하는 방식(지수 시간 복잡도)과 비교하면 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.