백준 4095 최대 정사각형

문제설명

접근방식

0과 1로 구성된 배열 정보를 통해서 1들로만 구성된 최대 정사가형의 너비 혹은 높이를 찾아주는 문제이다. 예제에 나와있는 배열을 그려가면서 정사각형을 찾다보면 문제의 핵심은 정사각형이라는 점을 이해할 수 있다. 만약 문제의 제시가 직사각형이었으면 훨씬 더 문제풀이가 복잡해질 수 있으나 문제에서 요구하는 것은 정사각형이기 때문에 상대적으로 쉽게 접근할 수 있다.

한 모서리를 기준으로 정사각형을 카운트하게 되면 간단하게 접근할 수 있다. 우측하단 모서리를 기준으로 정사각형의 최대 크기를 구한다고 했을 때 그 크기는 우,상단 방향의 3점들에서 얻은 값을 바탕으로 구할 수 있다. (i,j)의 포인트에서 정사각형의 최대너비를 구하다고 했을 때 (i, j-1,) , (i-1, j-1), (i-1, j)의 세 점을 기준으로 얻을 수 있는 정사각형의 공통최소너비에 1을 더한 값이 되게 된다. (i,j) 포인트에서의 최대 정사각형의 너비를 x라고 했을 때 (i-x+1, j), (i-x+!, j-x+1), (i,j-x+1), (i, j)의 네 모서리를 가지는 지점이고 이는 앞서 말한 세 지점에서 X-1의 너비를 가지면서 그 안에 속해있어야만 한다.

다음과 같은 방식으로 x-1 너비의 3개의 정사각형과 1너비의 정사각형이 하나가 만나서 x너비의 정사각형을 구성하게 된다.

if(arr[i][j]){
   dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1;
}
// dp[i][j]는 (i,j) 구할 수 있는 정사각형의 최대 너비 

C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int N, M;
  while(1){
    cin >> N >> M;
    if(N==0 && M==0)
      break;
    
    vector<vector<int>> arr(N+1, vector<int>(M+1));
    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
    int ans = 0;
    for(int i=1; i<=N; i++){
      for(int j=1; j<=M; j++){
        cin >> arr[i][j];
        if(arr[i][j]){
          dp[i][j] = 1;
          dp[i][j] += min(dp[i-1][j-1],min(dp[i][j-1], dp[i-1][j]));
        }
        ans = max(ans, dp[i][j]);
      }
    }
    cout << ans << '\n';
  }
}