[BOJ/C++] 1915: 가장 큰 정사각형

🏅 Gold 4

✏️ 솔루션

⭐️ DP로 풀이

0 0 0 0
0 1 1 1
0 1 1 1
0 1 1 1

위와 같이 3*3 크기의 사각형이 있다면 (1,1) 부터 왼쪽, 왼쪽 대각선 위, 위쪽 중에 최소값 + 1 으로 값을 갱신해 나가면 3*3 크기의 사각형의 마지막 인덱스인 (3,3) 의 값이 3으로 갱신됨으로서 3*3 크기의 사각형이 존재함을 기록할 수 있음

• 값이 1인 경우에 한해, 왼쪽, 왼쪽 대각선 위, 위쪽 인덱스가 모두 존재하려면 (1,1) 부터 탐색해야 함
  but 아래 경우처럼 탐색 대상이 아닌 인덱스에만 1이 존재하면서 최대 사각형이 1*1 인 경우는 count 되지 않는 예외 사항이 있을 수 있으므로 board 를 입력받을 때, 값이 1이면 answer 를 1로 갱신해줘야 함

0 0 0 0
0 0 0 0
1 0 0 0

• 탐색할 때, 자기 자신이 0이 아닐 경우에만 탐색하고 최대값을 갱신하도록 함

📌 self feedback

DP 문제가 그렇듯이 규칙성을 파악하는 것이 관건이었음
정사각형이 형성되면 그 여부를 어떻게 기록할지, 최대값은 어떻게 기록할지, 3*3 크기를 넘어서면 사각형 윤곽 이외에 사각형 내부도 1로 채워져 있는지 확인해야 하는데 어떻게 하면 단계를 축소할 수 있을지가 너무 어려웠음..

✏️ code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    int n,m,ans=0;
    int dp[1001][1001];
    cin >> n >> m;

    for(int i=0;i<n;i++) {
        string s;
        cin >> s;
        for(int j=0;j<m;j++) {
            dp[i][j]=s[j]-'0';
            if(dp[i][j]==1) ans=1;
        }

    }

    for(int i=1;i<n;i++) {
        for(int j=1;j<m;j++) {
            if(dp[i][j]!=0) {
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }

    cout << ans*ans;

}