파이썬으로 열 재배열 후 가장 큰 '1' 부분행렬의 넓이 구하기

문제 설명

m x n 크기의 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 우리는 이 행렬의 열(column)을 임의의 순서대로 자유롭게 재배열할 수 있습니다. 목표는 몇 번의 열 교환 작업을 수행한 뒤, 행렬 내에서 모든 요소가 1로 이루어진 가장 큰 부분행렬(submatrix)의 넓이를 구하는 것입니다.

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

열을 적절히 교환하면 아래와 같은 형태가 됩니다.

위 예시에서 빨간색으로 표시된 영역은 2 x 2 크기의 정사각형 부분행렬로, 네 개의 요소가 모두 1입니다. 따라서 출력 결과는 4가 됩니다.

풀이 접근 방법

이 문제는 히스토그램(histogram) 기반 최대 직사각형 문제와 유사한 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 행을 기준으로 위쪽 방향으로 연속된 1의 개수(높이)를 계산한 뒤, 각 행마다 오름차순 정렬을 활용해 최대 넓이를 구하는 것입니다.

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

• row := 행렬의 행 개수, col := 행렬의 열 개수로 설정합니다.
• j를 0부터 col - 1까지 반복하며:
  • i를 1부터 row - 1까지 반복하며:
    • matrix[i][j]가 1이라면, matrix[i][j]에 matrix[i-1][j]를 더합니다. 즉, 해당 위치에서 위로 연속된 1의 개수를 누적합니다.
• ans := 0으로 초기화합니다.
• i를 0부터 row - 1까지 반복하며:
  • matrix[i] 리스트를 오름차순으로 정렬합니다.
  • j를 col - 1부터 0까지 감소시키며 반복합니다:
    • matrix[i][j]가 0이면 반복문을 종료합니다.
    • ans = max(ans, (col - j) * matrix[i][j])로 최댓값을 갱신합니다.
• ans를 반환합니다.

여기서 (col - j)는 현재 값 이상인 원소의 개수를 의미하고, matrix[i][j]는 그 높이를 의미하므로 두 값을 곱하면 가능한 부분행렬의 넓이가 됩니다.

예제 코드

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

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

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

입력

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

출력

4

정리

이 알고리즘은 먼저 각 셀을 기준으로 세로 방향의 연속된 1의 개수를 누적하여 히스토그램 형태로 변환한 후, 각 행을 정렬하여 왼쪽부터 차례대로 넓이를 계산하는 방식입니다. 시간 복잡도는 O(row × col × log col)로, 정렬 단계가 지배적입니다. 열의 순서를 자유롭게 바꿀 수 있다는 조건 덕분에 정렬만으로 최적 배치를 찾을 수 있다는 점이 이 문제의 핵심 포인트입니다.