C++로 구현하는 1로만 이루어진 최대 크기 직사각형 이진 부분행렬 찾기

문제 개요

이 튜토리얼에서는 1로만 이루어진 최대 크기의 직사각형 이진 부분행렬을 찾는 프로그램을 다룹니다.

0과 1로 구성된 2차원 행렬이 주어졌을 때, 우리의 목표는 오직 1만 포함하는 가장 큰 부분행렬의 넓이를 구하는 것입니다.

접근 방법

이 문제는 잘 알려진 '히스토그램에서 가장 큰 직사각형' 알고리즘을 행 단위로 확장하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

1. 첫 번째 행을 하나의 히스토그램으로 보고 최대 직사각형 넓이를 계산합니다.
2. 이후 각 행에 대해, 바로 위 행의 값에 현재 값을 더해 누적 히스토그램을 만듭니다. 즉, 각 열에서 위쪽 방향으로 연속된 1의 개수가 해당 열의 막대 높이가 됩니다.
3. 매 행마다 스택 기반 히스토그램 알고리즘(maxHist)을 적용해 최대 넓이를 갱신합니다.

이 방식의 시간 복잡도는 O(R×C)로, 단순 브루트포스(O(R²×C²))보다 훨씬 효율적입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4

// 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 함수
int maxHist(int row[]) {
    stack<int> result;   // 인덱스를 저장하는 스택
    int top_val;         // 스택 꼭대기의 막대 높이
    int max_area = 0;    // 지금까지 찾은 최대 넓이
    int area = 0;        // 현재 계산 중인 넓이
    int i = 0;

    while (i < C) {
        // 스택이 비었거나 현재 막대가 스택 꼭대기의 막대보다 높거나 같으면 push
        if (result.empty() || row[result.top()] <= row[i])
            result.push(i++);
        else {
            // 현재 막대가 더 낮으면 pop 하며 넓이 계산
            top_val = row[result.top()];
            result.pop();
            area = top_val * i;
            if (!result.empty())
                area = top_val * (i - result.top() - 1);
            max_area = max(area, max_area);
        }
    }
    // 스택에 남아 있는 막대들 처리
    while (!result.empty()) {
        top_val = row[result.top()];
        result.pop();
        area = top_val * i;
        if (!result.empty())
            area = top_val * (i - result.top() - 1);
        max_area = max(area, max_area);
    }
    return max_area;
}

// 1로만 이루어진 최대 직사각형 부분행렬의 넓이를 반환하는 함수
int maxRectangle(int A[][C]) {
    // 첫 번째 행부터 시작
    int result = maxHist(A[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
            // 현재 칸이 1이면 위쪽 행의 누적값을 더함
            if (A[i][j])
                A[i][j] += A[i - 1][j];
        result = max(result, maxHist(A[i]));
    }
    return result;
}

int main() {
    int A[][C] = {
        { 0, 1, 1, 0 },
        { 1, 1, 1, 1 },
        { 1, 1, 1, 1 },
        { 1, 1, 0, 0 },
    };
    cout << "Area of maximum rectangle is " << maxRectangle(A);
    return 0;
}

실행 결과

Area of maximum rectangle is 8

동작 설명

위 예제 행렬에서 세 번째 행까지 누적했을 때 히스토그램은 [4, 4, 4, 2]가 되며, 여기서 높이 4 × 너비 2 = 8인 직사각형이 최대 넓이가 됩니다. 실제로 두 번째~세 번째 행, 첫 번째~두 번째 열에 해당하는 2×4 영역이 정답입니다.