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

문제

n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

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

위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.

입력

첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

풀이

왼쪽 위부터 오른쪽 아래까지 2차원 배열의 모든 인덱스를 확인한다.
해당 인덱스 [x][y]를 [x - 1][y], [x][y - 1], [x - 1][y - 1] 중 최소값으로 갱신한다.
각 인덱스의 값은 해당 위치에서 왼쪽 위 방향으로 만들 수 있는 가장 큰 정사각형의 한 변의 길이이다.
갱신한 인덱스 중 가장 큰 값이 현재 배열에서 가장 큰 정사각형의 한 변의 길이이므로,
(가장 큰 값) ^ 2 를 출력한다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

void find_max(void);
void input(void);

int square[1001][1001];
int n, m, result;

int main(void)
{
    input();
    find_max();

    return (0);
}

void input(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    int i = 0;
    while (++i <= n)
    {
        int j = 0;
        while (++j <= m)
        {
            char input;
            cin >> input;
            square[i][j] = input - '0';
        }
    }

    return ;
}

void find_max(void)
{
    int x = 0;
    while (++x <= n)
    {
        int y = 0;
        while (++y <= m)
        {
            if (square[x][y] != 0)
            {
                square[x][y] = min({square[x - 1][y], square[x][y - 1], square[x - 1][y - 1]}) + 1;
                result = max(result, square[x][y]);
            }
        }
    }

    cout << result * result;

    return ;
}

성공 !