C++로 모두 1로 이루어진 최대 크기의 직사각형 이진 부분행렬 찾기

문제 개요

이 문제에서는 n×m 크기의 2차원 행렬 bin[][]가 주어지며, 행렬의 각 요소는 0 또는 1의 이진 값입니다. 우리의 목표는 모든 요소가 1로 이루어진 가장 큰 직사각형 부분행렬을 찾아 그 최대 면적을 반환하는 프로그램을 작성하는 것입니다.

예제를 통해 문제를 살펴보겠습니다.

입력

bin[][] = {
    {1, 0, 1, 1, 1},
    {0, 1, 1, 1, 1},
    {0, 0, 1, 1, 1},
    {1, 1, 1, 1, 1}
}

출력

12

설명

다음 직사각형 영역이 가장 넓은 면적을 가집니다.

1, 1, 1
1, 1, 1
1, 1, 1
1, 1, 1

풀이 접근 방식

이 문제를 해결하려면 1로만 구성된 가장 큰 직사각형 부분행렬을 찾아야 합니다. 이를 위해 각 행을 기준으로, 현재 행까지 포함하여 만들 수 있는 직사각형의 최대 면적을 순차적으로 계산합니다.

구체적인 과정은 다음과 같습니다.

• 먼저 각 열에 대해 현재 요소까지 연속해서 나타나는 1의 개수, 즉 '높이'를 계산합니다. 현재 행의 요소가 1이면 바로 위 행의 누적 값에 1을 더하고, 0이면 해당 열의 높이를 0으로 초기화합니다.
• 그다음 인접한 열 중 같은 높이 이상인 요소들을 하나의 직사각형으로 묶습니다. 높이가 서로 다르면 가장 작은 높이를 기준으로 면적을 계산합니다.
• 이 과정은 사실상 '히스토그램에서 가장 큰 직사각형 찾기' 문제와 동일하며, 스택(stack)을 활용하면 한 행당 O(C) 시간 안에 처리할 수 있습니다.
• 모든 행에 대해 계산한 면적 중 가장 큰 값이 곧 정답이 됩니다.

구현 예제

솔루션의 동작을 보여주는 C++ 프로그램입니다.

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

int calcAreaTillRow(int row[]) {
    stack<int> area1s;
    int tos;
    int maxArea = 0;
    int curArea = 0;
    int i = 0;
    while (i < C) {
        if (area1s.empty() || row[area1s.top()] <= row[i])
            area1s.push(i++);
        else {
            tos = row[area1s.top()];
            area1s.pop();
            curArea = tos * i;
            if (!area1s.empty())
                curArea = tos * (i - area1s.top() - 1);
            maxArea = max(curArea, maxArea);
        }
    }
    while (!area1s.empty()) {
        tos = row[area1s.top()];
        area1s.pop();
        curArea = tos * i;
        if (!area1s.empty())
            curArea = tos * (i - area1s.top() - 1);
        maxArea = max(curArea, maxArea);
    }
    return maxArea;
}

int calcmaxRecSubMat1(int bin[][C]) {
    int result = calcAreaTillRow(bin[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
            if (bin[i][j])
                bin[i][j] += bin[i - 1][j];
        result = max(result, calcAreaTillRow(bin[i]));
    }
    return result;
}

int main() {
    int bin[][C] = {
        {1, 0, 1, 1, 1},
        {0, 1, 1, 1, 1},
        {0, 0, 1, 1, 1},
        {1, 1, 1, 1, 1}
    };
    cout << "모두 1로 이루어진 최대 크기 직사각형 이진 부분행렬의 면적은 " << calcmaxRecSubMat1(bin);
    return 0;
}

출력 결과

모두 1로 이루어진 최대 크기 직사각형 이진 부분행렬의 면적은 12

복잡도 분석

각 행마다 스택 기반 히스토그램 알고리즘을 한 번씩 수행하므로 전체 시간 복잡도는 O(R×C)이며, 스택에 사용되는 추가 공간 복잡도는 O(C)입니다. 모든 부분행렬을 일일이 확인하는 완전 탐색 방식에 비해 훨씬 효율적으로 문제를 해결할 수 있습니다.