C++로 모든 원소가 동일한 최대 크기 정사각형 부분 행렬 찾기

문제 개요

이 문제에서는 N×N 크기의 행렬 mat[]가 주어지며, 우리의 목표는 모든 원소가 동일한 가장 큰 정사각형 부분 행렬을 찾는 것입니다.

즉, 주어진 행렬 안에서 모든 원소의 값이 서로 같은 부분 행렬 중 최대 크기를 구해야 합니다.

예제로 문제 이해하기

입력: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
출력: 2

설명: a₁₁, a₁₂, a₂₁, a₂₂로 구성된 2×2 부분 행렬의 모든 원소가 동일하므로, 정답은 2가 됩니다.

해결 접근 방법

1. 브루트 포스(완전 탐색)

가장 단순한 방법은 행렬의 모든 원소를 순회하면서 가능한 모든 부분 행렬을 검사하여 원소가 모두 같은지 확인하는 것입니다. 하지만 이 방식은 시간 복잡도가 O(n³) 이상으로 증가하고, 각 부분 행렬을 생성·검사하는 데 추가로 O(n²)의 시간이 걸리므로 입력 크기가 클 경우 매우 비효율적입니다.

2. 동적 계획법(Dynamic Programming)

더 효율적인 대안은 동적 계획법을 활용하는 것입니다. DP 테이블 DP[i][j]에는 (i, j) 위치를 오른쪽 아래 꼭짓점으로 하는, 모든 원소가 동일한 정사각형 부분 행렬의 최대 크기를 저장합니다. 이때 현재 원소의 인접 원소들을 고려하여 조건을 만족하는 가장 큰 행렬로 확장할 수 있는지 판단합니다.

현재 원소의 위쪽, 왼쪽, 왼쪽 위 대각선 세 방향의 원소가 모두 현재 원소와 같다면, 기존 부분 행렬의 크기를 1만큼 늘릴 수 있습니다. 이 경우 점화식은 다음과 같습니다.

$DP[i][j]\:=\:min(DP[i-1][j]\,,\:DP[i][j-1],\:DP[i-1][j-1])\:+\:1$

반대로 세 원소 중 하나라도 다르다면, 해당 위치 자체만으로 새로운 부분 행렬이 시작되므로 다음과 같이 설정합니다.

DP[i][j] = 1

첫 번째 행과 첫 번째 열은 확장할 수 없으므로 항상 1로 초기화됩니다. 전체 DP 테이블을 채운 뒤 그중 최댓값이 곧 정답이 되며, 이 방법의 시간 복잡도는 O(n²)입니다.

구현 예제

다음 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include<bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
int findmaxSqMatSize(int mat[][m]){
   int DP[n][m];
   memset(DP, 0, sizeof(DP));
   int maxSqMatSize = 0;
   for (int i = 0 ; i < n ; i++){
      for (int j = 0 ; j < m ; j++){
         if (i == 0 || j == 0)
            DP[i][j] = 1;
         else{
            if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1])
               DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1;
            else DP[i][j] = 1;
         }
         maxSqMatSize = max(maxSqMatSize, DP[i][j]);
      }
   }
   return maxSqMatSize;
}
int main(){
   int mat[n][m] = { {2, 1, 4, 3},
   {5, 1, 1, 7},
   {1, 1, 1, 4},
   {9, 4, 6, 0}};
   cout<<"모든 원소가 동일한 최대 정사각형 부분 행렬의 크기: "<<findmaxSqMatSize(mat);
   return 0;
}

실행 결과

모든 원소가 동일한 최대 정사각형 부분 행렬의 크기: 2