백준 1915번 - 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

0과 1로 된 배열에서 가장 큰 정사각형의 크기를 묻는 문제다.

즉, 1로만 이루어진 정사각형을 알아내야 한다.

문제에 접근할 때 (i,j)를 기준으로

(i-1,j) / (i,j-1) / (i-1,j-1) 각각 정사각형의 길이를 알면

(i,j)에서 위의 3가지 경우 중에서 가장 작은 정사각형 길이를 가진 것보다 1만 큼 더 긴 정사각형을 가질 수 있다.

왜냐하면 (i,j)에서 다시 1만큼 추가되기 때문이다.

1부터 n, m까지 (i,j)의 값이 1이라면

3가지 경우 중에 가장 작은 길이보다 1을 더 추가한 길이가 (i,j)의 정사각형 길이가 될 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n,m;
    cin>>n>>m;
    
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            dp[i][j]=c-48;
        }
    }
    
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dp[i][j]){
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    
    cout<<ans*ans<<endl;
    return 0;
}