이 문제에서는 0과 1로만 이루어진 n×n 크기의 2차원 행렬이 주어집니다. 우리의 목표는 1의 개수가 0의 개수보다 정확히 1개 더 많은 부분행렬(submatrix) 중에서 가장 넓은 영역의 크기를 구하는 프로그램을 작성하는 것입니다.
문제 이해를 위한 예시
입력
bin[N][N] = {
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1}
}출력
9
설명
부분행렬 : bin[1][0], bin[1][1], bin[1][2] bin[2][0], bin[2][1], bin[2][2] bin[3][0], bin[3][1], bin[3][2] 위 영역이 1의 개수가 0의 개수보다 1개 많은 가장 큰 부분행렬입니다. 0의 개수 = 4 1의 개수 = 5
즉, 3×3 크기의 부분행렬(넓이 9)이 조건을 만족하는 최대 영역입니다.
해결 접근 방법
방법 1: 완전 탐색 (브루트 포스)
가장 단순한 방법은 행렬에서 만들 수 있는 모든 부분행렬을 검사하고, 그중 조건을 만족하면서 넓이가 가장 큰 값을 반환하는 것입니다.
이 방법은 생각하기 쉽고 구현도 간단하지만, 여러 겹의 반복문이 중첩되어 시간 복잡도가 O(n⁴)에 달합니다. 따라서 입력 크기가 커지면 비효율적입니다.
방법 2: 열 고정 + 누적 합 기반 탐색 (효율적인 방법)
더 효과적인 아이디어는 다음과 같습니다.
- 행렬의 왼쪽 열(left)과 오른쪽 열(right)을 고정합니다.
- 고정된 두 열 사이의 각 행에 대해, 1은 +1, 0은 -1로 변환하여 행별 합을 계산합니다.
- 이렇게 만들어진 1차원 배열에서 합이 1이 되는 가장 긴 연속 부분 배열을 찾습니다. 합이 1이라는 것은 곧 1의 개수가 0의 개수보다 1개 많다는 의미이기 때문입니다.
- 해시 맵(unordered_map)을 활용해 누적 합을 저장하면 각 열 쌍에 대해 O(n) 만에 최장 길이를 구할 수 있습니다.
이 방식의 전체 시간 복잡도는 O(n³)으로, 완전 탐색보다 상당히 개선됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// 합이 1이 되는 가장 긴 연속 부분 배열의 길이를 찾는 함수
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
unordered_map<int, int> subArr;
int sumVal = 0, maxSubArrLen = 0;
for (int i = 0; i < n; i++) {
sumVal += row[i];
// 처음부터 현재 위치까지의 합이 1인 경우
if (sumVal == 1) {
startInd = 0;
finishInd = i;
maxSubArrLen = i + 1;
}
else if (subArr.find(sumVal) == subArr.end())
subArr[sumVal] = i;
// 누적 합이 (현재 합 - 1)이었던 지점이 있으면
// 그 다음 위치부터 현재까지의 구간 합이 1이 됨
if (subArr.find(sumVal - 1) != subArr.end()) {
int currLen = (i - subArr[sumVal - 1]);
if (maxSubArrLen < currLen)
startInd = subArr[sumVal - 1] + 1;
finishInd = i;
maxSubArrLen = currLen;
}
}
return maxSubArrLen;
}
// 최대 부분행렬 넓이를 구하는 함수
int largestSubmatrix(int bin[SIZE][SIZE], int n){
int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,
finishInd;
for (int left = 0; left < n; left++) {
memset(rows, 0, sizeof(rows));
for (int right = left; right < n; right++) {
// right 열을 rows 배열에 반영 (1은 +1, 0은 -1)
for (int i = 0; i < n; ++i){
if(bin[i][right] == 0)
rows[i] -= 1;
else
rows[i] += 1;
}
longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
currArea = (finishInd - startInd + 1) * (right - left + 1);
if ((longLen != 0) && (maxSubMatArea < currArea)) {
maxSubMatArea = currArea;
}
}
}
return maxSubMatArea;
}
int main(){
int bin[SIZE][SIZE] = {
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 1 }
};
int n = 4;
cout<<"1의 개수가 0의 개수보다 1개 많은 최대 부분행렬의 넓이는 "
<<largestSubmatrix(bin, n);
return 0;
}실행 결과
1의 개수가 0의 개수보다 1개 많은 최대 부분행렬의 넓이는 9
핵심 정리
- 2차원 행렬 문제를 열 쌍을 고정하여 1차원 배열 문제로 변환하는 것이 이 풀이의 핵심입니다.
- 누적 합(prefix sum)과 해시 맵을 사용하면 '합이 1인 최장 부분 배열'을 선형 시간에 찾을 수 있습니다.
- 시간 복잡도는 O(n³), 공간 복잡도는 O(n)입니다.