C++로 푸는 최대 직사각형(Maximal Rectangle) 문제: 스택 기반 히스토그램 알고리즘 완벽 정리

0과 1로 이루어진 2차원 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 이때 1로만 채워진 가장 큰 직사각형을 찾아 그 넓이를 반환하는 것이 이번 문제의 목표입니다.

이 문제는 각 행을 히스토그램으로 변환한 뒤, 스택(stack)을 활용해 히스토그램에서 가장 큰 직사각형을 구하는 고전적인 기법으로 효율적으로 해결할 수 있습니다. 전체 시간 복잡도는 O(n × m)으로, 완전 탐색 방식보다 훨씬 빠른 성능을 보입니다.

해결 접근 방식

핵심 아이디어는 다음과 같습니다. 각 행을 순회하면서 해당 열까지 연속된 1의 개수를 높이(height)로 누적하면, 매 행마다 하나의 히스토그램이 만들어집니다. 이 히스토그램에 대해 "가장 큰 직사각형" 알고리즘을 적용하면 됩니다.

getAns 함수 (히스토그램 최대 직사각형 계산)

배열 a를 인자로 받는 getAns 함수를 정의합니다.
스택 st를 생성하고, i := 0, ans := 0으로 초기화합니다.
i < a.size()인 동안 다음을 반복합니다:
- 스택이 비어 있거나 a[i]가 스택 꼭대기 값 이상이면 i를 st에 삽입하고 i를 1 증가시킵니다.
- 그렇지 않다면:
  - height := a[st.top()]으로 설정하고 스택에서 제거(pop)합니다.
  - width는 스택이 비어 있으면 i, 그렇지 않으면 i − st.top() − 1로 계산합니다.
  - area := height × width
  - ans를 ans와 area 중 더 큰 값으로 갱신합니다.
스택이 빌 때까지 남은 원소에 대해서도 동일하게 처리합니다:
- height := a[st.top()], pop 수행
- width는 스택이 비면 배열 전체 길이, 아니면 a.size() − st.top() − 1
- area := height × width를 계산해 ans를 갱신합니다.
최종적으로 ans를 반환합니다.

maximalRectangle 메인 로직

ans := 0, n := x.size()로 초기화합니다.
n이 0이면(빈 행렬) 0을 반환합니다.
m := x[0].size()로 열의 개수를 구합니다.
크기가 m인 height 배열을 생성합니다.
i를 0부터 n − 1까지 순회하면서:
- j를 0부터 m − 1까지 순회하며 x[i][j] == '1'이면 height[j]를 1 증가시키고, 그렇지 않으면 height[j] := 0으로 초기화합니다.
- ans를 ans와 getAns(height) 결과 중 최댓값으로 갱신합니다.
모든 행을 처리한 후 ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 과정을 더 명확히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int getAns(vector <int> a){
      stack <int> st;
      int i = 0;
      int ans = 0;
      while(i<a.size()){
         if(st.empty()||a[i]>=a[st.top()]){
            st.push(i);
            i++;
         } else{
            int height = a[st.top()];
            st.pop();
            int width = st.empty()?i:i-st.top()-1;
            int area = height * width;
            ans = max(ans,area);
         }
      }
      while(!st.empty()){
         int height = a[st.top()];
         st.pop();
         int width = st.empty()?a.size():a.size() - st.top()-1;
         int area = height * width;
         ans = max(ans,area);
      }
      return ans;
   }
   int maximalRectangle(vector<vector<char>>& x) {
      int ans = 0;
      int n = x.size();
      if(!n)return 0;
      int m = x[0].size();
      vector <int> height(m);
      for(int i =0;i<n;i++){
         for(int j =0;j<m;j++){
            if(x[i][j] == '1')height[j]++;
            else height[j] = 0;
         }
         ans = max(ans, getAns(height));
      }
      return ans;
   }
};
main(){
   vector<vector<char>> v = {
      {'1','0','1','0','0'},
      {'1','0','1','1','1'},
      {'1','1','1','1','1'},
      {'1','0','0','1','0'}
   };
   Solution ob;
   cout << (ob.maximalRectangle(v));
}

입력

{{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
}

출력

결과 분석

위 입력 행렬에서 최대 직사각형은 세 번째 행을 포함한 영역, 즉 행 인덱스 1~2, 열 인덱스 2~4에 걸친 1로 이루어진 2×3 직사각형입니다. 따라서 최대 넓이는 6이 반환됩니다.

이처럼 스택 기반 히스토그램 기법을 활용하면 각 행마다 O(m) 시간 안에 최대 직사각형을 구할 수 있어, 전체 문제를 O(n × m)의 효율적인 시간 복잡도로 해결할 수 있습니다.