파이썬으로 열 재배열 후 1만으로 이루어진 최대 부분행렬 면적 찾기

0과 1로 이루어진 이진 행렬(binary matrix)이 있다고 가정해 보겠습니다. 이때 우리는 열(column)을 원하는 만큼 자유롭게 재배열할 수 있으며, 그 후 1만으로 이루어진 가장 큰 부분행렬의 면적을 구해야 합니다.

문제 예시

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

이 경우 정답은 4입니다. 열을 다음과 같이 재배열하면 두 번째·세 번째 행에 걸쳐 크기 4짜리 직사각형(주황색 영역)을 만들 수 있기 때문입니다.

풀이 접근 방법

이 문제는 히스토그램(histogram) 기법과 정렬을 활용해 효율적으로 해결할 수 있습니다. 전체적인 해결 과정은 다음과 같습니다.

• n := 행렬의 행(row) 개수
• m := 행렬의 열(column) 개수
• ans := 0
• i를 1부터 n-1까지 반복합니다.
  • j를 0부터 m-1까지 반복합니다.
    • matrix[i][j]가 1이라면, 바로 위 행의 값을 더해 위쪽으로 연속된 1의 높이를 누적합니다.
      matrix[i][j] := matrix[i][j] + matrix[i-1][j]
• 행렬의 각 행에 대해 다음을 수행합니다.
  • 해당 행을 오름차순으로 정렬합니다.
  • j를 m-1부터 0까지 1씩 감소시키며 반복합니다.
    • ans := ans와 row[j] × (m - j) 중 더 큰 값으로 갱신
• ans를 반환합니다.

알고리즘이 동작하는 원리

첫 번째 단계에서는 각 칸을 기준으로 위쪽 방향으로 연속해서 이어지는 1의 개수, 즉 '히스토그램 막대의 높이'를 계산합니다. 두 번째 단계에서 각 행을 오름차순으로 정렬하면, 특정 위치 j부터 행의 끝까지는 모두 row[j] 이상의 높이를 가지게 됩니다. 따라서 높이가 row[j]인 직사각형이 가질 수 있는 최대 너비는 (m - j)이며, 가능한 모든 j에 대해 면적을 검사하면 최댓값을 구할 수 있습니다. 이 방식의 시간 복잡도는 O(n × m log m)입니다.

구현 예제

아래 파이썬 코드를 통해 실제 구현을 확인해 보겠습니다.

def solve(matrix):
    n, m = len(matrix), len(matrix[0])
    ans = 0
    for i in range(1, n):
        for j in range(m):
            if matrix[i][j]:
                matrix[i][j] += matrix[i-1][j]
    for row in matrix:
        row.sort()
        for j in range(m-1, -1, -1):
            ans = max(ans, row[j] * (m - j))
    return ans

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

입력

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

출력

4