[BOJ] 1915번 : 가장 큰 정사각형(C++)

문제 링크 : 백준 1915번

[문제 접근]

DP를 이용해 풀었다.
1행과 1열을 제외하고 한 점에서 (-1,-1), (-1,0), (0,-1) 중에 작은 것이 해당 점을 제외한 정사각형의 넓이이다.
따라서 현재 정점이 1이라면 해당 점까지의 정사각형 넓이를 추가로 더해주면 된다.

ex)
1 1 1 1 1 1
1 1 1 -> 1 2 2
1 1 1 1 2 3

0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 1
1 1 1 0 -> 1 1 2 0
0 0 1 0 0 0 1 0

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n,m,area=0;
int arr[1001][1001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0 ; i<n ; i++) {
        string s;
        cin >> s;
        for(int j=0 ; j<s.size() ; j++) {
            arr[i][j] = s[j]-'0';
        }
    }
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            if(arr[i][j] == 1) {
                if(i == 0 || j == 0) {
                    area = max(area, arr[i][j]);
                } else {
                    int temp = min(arr[i-1][j-1], min(arr[i][j-1], arr[i-1][j]));
                    arr[i][j] += temp;
                    area = max(area, arr[i][j]);
                }
            }
        }
    }
    cout << area*area;

    return 0;
}