백준[1915] 가장 큰 정사각형

문제 설명

문제 링크

http://icpc.me/1915

1915번: 가장 큰 정사각형

풀이

dp로 해결할 수 있다.

dp 점화식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]), (i, j는 배열 인덱스)로 정의할 수 있다.

예시

위의 그림과 같은 예제가 있을 때 (2, 2) 인덱스에서 한 변의 길이가 2인 정사각형이 만들어지기 위해서는 왼쪽, 위, 왼쪽 위 가 모두 1이어야 한다.

이 말을 바꿔 말하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 1 이어야 한다. 

(5, 5)에서 한 변의 길이가 3인 정사각형을 만들기 위해서는 왼쪽, 위, 왼쪽위 모두 한변의 길이가 2인 정사각형을 만들 수 있어야 한다.

이 말도 일반화하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 2이어야 한다.

일반화하면, (i, j)에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1이다

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int arr[1003][1003], ans;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", &arr[i][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i][j]) {
                arr[i][j] = min(arr[i - 1][j], min(arr[i][j - 1], arr[i - 1][j - 1])) + 1;
                ans = max(arr[i][j], ans);
            }
        }
    }
    printf("%d", ans * ans);
}