문제 개요
이 튜토리얼에서는 1의 개수가 0의 개수보다 정확히 하나 더 많은 부분 행렬(sub-matrix) 중에서 넓이가 최대인 것을 찾는 프로그램을 C++로 구현하는 방법을 알아봅니다.
입력으로는 0과 1로만 이루어진 N×N 행렬이 주어지며, 목표는 조건을 만족하는 부분 행렬의 시작 위치(왼쪽 상단, 오른쪽 하단 좌표)와 최대 넓이를 구하는 것입니다.
알고리즘 접근 방식
핵심 아이디어는 2차원 행렬 문제를 1차원 배열 문제로 변환하는 것입니다.
- 각 셀의 값에서 1은 +1, 0은 -1로 치환합니다. 그러면 '1이 0보다 하나 더 많은 구간'은 '합이 1인 구간'과 동일한 의미가 됩니다.
- 왼쪽 열(left)과 오른쪽 열(right)의 모든 조합에 대해 두 열 사이의 값을 행(row)별로 누적하여 임시 1차원 배열(temp)을 생성합니다.
- 이 1차원 배열에서 누적합(prefix sum)과 해시맵(unordered_map)을 활용해 합이 1이 되는 가장 긴 연속 부분 배열을 O(n) 시간에 찾습니다.
- 찾은 부분 배열의 길이 × 현재 열의 폭으로 넓이를 계산하고, 기존 최대 넓이보다 크면 해당 좌표와 넓이를 갱신합니다.
전체 시간 복잡도는 세 겹의 반복문 때문에 O(n³)이며, n이 수백 수준까지는 충분히 빠르게 동작합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// 합이 1이 되는 가장 긴 부분 배열의 길이를 찾는 함수
int lenOfLongSubarr(int arr[], int n, int& start, int& finish) {
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
// 처음부터 i까지의 합이 1인 경우
if (sum == 1) {
start = 0;
finish = i;
maxLen = i + 1;
}
else if (um.find(sum) == um.end()) um[sum] = i;
// sum - 1이 이전에 등장했다면, 그 이후 구간의 합은 1
if (um.find(sum - 1) != um.end()) {
if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1;
finish = i;
maxLen = i - um[sum - 1];
}
}
return maxLen;
}
// 최대 넓이의 부분 행렬을 찾는 함수
void largestSubmatrix(int mat[SIZE][SIZE], int n) {
int finalLeft, finalRight, finalTop, finalBottom;
int temp[n], maxArea = 0, len, start, finish;
for (int left = 0; left < n; left++) {
memset(temp, 0, sizeof(temp));
for (int right = left; right < n; right++) {
for (int i = 0; i < n; ++i)
temp[i] += mat[i][right] == 0 ? -1 : 1;
len = lenOfLongSubarr(temp, n, start, finish);
if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) {
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
maxArea = (finish - start + 1) * (right - left + 1);
}
}
}
cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";
cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";
cout << "Maximum area: " << maxArea;
}
int main() {
int mat[SIZE][SIZE] = {
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 1 }
};
int n = 4; largestSubmatrix(mat, n);
return 0;
}
출력 결과
(Top, Left): (1, 1)
(Bottom, Right): (3, 3)
Maximum area: 9
동작 원리 상세 설명
lenOfLongSubarr 함수가 핵심 로직입니다. 배열을 순회하면서 누적합(sum)을 유지하고, 해시맵에는 각 누적합이 처음 등장한 인덱스를 저장합니다.
- sum == 1인 경우: 인덱스 0부터 i까지 전체 구간이 이미 조건을 만족하므로 즉시 갱신합니다.
- sum - 1이 해시맵에 존재하는 경우: 과거 어느 시점 j에서 누적합이 (현재 누적합 - 1)이었다면, 구간 [j+1, i]의 합은 정확히 1이 됩니다. 이를 통해 조건을 만족하는 가장 긴 구간을 찾아낼 수 있습니다.
위 실행 예제에서는 (1,1)부터 (3,3)까지의 3×3 부분 행렬이 선택되었으며, 해당 영역의 1은 5개, 0은 4개로 조건(1의 개수 = 0의 개수 + 1)을 만족하면서 넓이 9로 최대가 됩니다.