C++ 프로그램에서 1의 개수가 0의 개수보다 1개 많은 최대 부분행렬 영역

이 문제에서는 이진수(0/1)로 구성된 nXn 크기의 2차원 행렬이 제공됩니다. 우리의 임무는 0보다 1이 더 많은 최대 부분행렬 영역을 찾는 프로그램을 만드는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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

출력

9

설명

submatrix :
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]
is the largest subarray with more 1’s one more than 0’s.
Number of 0’s = 4
Number of 1’s = 5

해결 방법

간단한 접근 방식은 행렬에서 가능한 모든 부분행렬을 찾은 다음 모두에서 최대 면적을 반환하는 것입니다.

이 접근 방식은 생각하고 구현하기 쉽지만 시간이 많이 걸리고 O(n^4) 순서의 시간 복잡성을 만드는 루프의 중첩이 필요합니다. .그래서 더 효과적인 방법을 하나 더 논의해 보겠습니다.

여기서 아이디어는 행렬의 왼쪽과 오른쪽에 있는 열을 고정한 다음 0의 개수가 1의 개수보다 하나 많은 가장 큰 부분배열을 찾는 것입니다. 각 행에서 합계를 계산한 다음 누적합니다. 1의 개수가 0의 개수보다 1개 많은 최대 영역을 찾으려면.

예

우리 솔루션의 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
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];
      if (sumVal == 1) {
         startInd = 0;
         finishInd = i;
         maxSubArrLen = i + 1;
      }
      else if (subArr.find(sumVal) == subArr.end())
         subArr[sumVal] = i;
      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++) {
         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<<"The maximum sub−matrix area having count of 1’s one more
   than count of 0’s is "<<largestSubmatrix(bin, n);
   return 0;
}

출력

The maximum sub-matrix area having count of 1’s one more than count of
0’s is 9