(골드 4)백준 1915: 가장 큰 정사각형

문제

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

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

입력

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

출력

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

---

핵심

문제와 같다.

---

내가 작성한 코드

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

int num[1001][1001];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        string temp;
        cin >> temp;

        int j = 1;
        for (auto ele : temp)
        {
            num[i][j] = ele - 48;
            j++;
        }
    }

    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (num[i][j])
            {
                num[i][j] = min({num[i - 1][j], num[i - 1][j - 1], num[i][j - 1]}) + 1;
                result = max(result, num[i][j]);
            }
        }
    }
    
    cout << result * result;

    return 0;
}

---

풀이

이번 문제는 접근하는 것이 어려웠지만 코드는 간결하고 쉽게 짤 수 있었다.

특정 좌표값을 기준으로 좌측, 위, 좌측윗 대각선에 전부 숫자가 표시되어 있으면 사각형이 만들어진다.

 

1. 배열을 입력받는다.

2. 첫좌표(1, 1)를 기준으로 하나씩 배열을 훑는다.

3. (x, y)좌푯값이 1인 경우 (x-1, y), (x, y-1), (x-1, y-1), (x, y) 중 가장 작은 값에 +1을 하여 저장한다.
4. 3을 반복하며 가장 큰 값을 저장하여 제곱해 출력한다.