[BAE/<JOON> 문제풀이] 1915. 가장 큰 정사각형 (DP.039)

 

 

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

이게 왜 동적계획법 문제인지 모르겠다.

 

각각 위치에 무슨 정보를 써야 풀 수 있을까 고민하다가 그냥 브루트포스로 풀기로 했다.

 

각 지점을 왼쪽 위 꼭짓점으로 하는 정사각형의 존재여부를 검사한다.

 

주어지는 맵의 양변의 최대크기가 1000이므로

 

검사해야할 지점은 총 $10^6$개

 

각각의 검사 경우 갯수는  각각의 단계에 대해 $\sum\limits_{k=1}^{1000000}a_{k}$ 이므로

 

$a_{k}$ 를 적당한 시간에 연산 할 수 있다면 이 방법으로 충분히 풀 수 있다고 생각했다.

 

$a$를 $arr_{ij}$라고 하면 $i$, $j$를 왼쪽 상단 꼭짓점으로 하여 정사각형이 만들어 질 수 있는 경우의 최대 수는

 

$min(n-i, m-j)$개이다. $i$, $j$는 해당 지점 자체가 1인 정사각형이므로 이후, 외곽변들을 추가해나가며 0이 발견되면 

 

탐색을 중지하고 발견된 정사각형 변중 가장 긴 것을 최댓값으로 저장한다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, m;
vector<vector<int>> arr;

int main()
{
    cin >> n >> m;
    arr.resize(n + 1);
    int zs = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        arr[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            arr[i][j] = s[j - 1] - 48;
            zs += arr[i][j];
        }
    }

    int mx = 0;

    if (zs == 0) {
        cout << 0;
        return 0;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int di = n - i;
            int dj = m - j;
            int tc = di < dj ? di : dj;
            int sign = 0;
            if (tc <= mx || arr[i][j] == 0) continue;
            for (int t = 1; t <= tc; t++) {
                for (int k = i; k <= i + t; k++) {
                    if (arr[k][j + t] == 0) {
                        sign = 1;
                        break;
                    }
                }
                if (sign == 1) break;
                for (int k = j; k <= j + t; k++) {
                    if (arr[i + t][k] == 0) {
                        sign = 1;
                        break;
                    }
                }
                if (sign == 1) break;
                if (sign == 0) {
                    if (mx < t) mx = t;
                }
            }
        }
    }

    cout << (mx + 1) * (mx + 1);

    return 0;
}