[백준 1915번] 가장 큰 정사각형 (C++)

문제링크 : https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int arr[1001][1001];
int result = 0;

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

    cin >> N >> M;
    for(int i=1; i<=N; i++)
    {
        string s;
        cin >> s;
        for(int j=1; j<=M; j++)
        {
            arr[i][j] = s[j-1]-'0'; //문자열로 입력받고 숫자로 전환
        }
    }

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            if(!arr[i][j]) continue;
            arr[i][j] = min({arr[i-1][j], arr[i][j-1], arr[i-1][j-1]}) + 1; //좌, 좌상, 상 체크
            result = max(result, arr[i][j]); //가장 큰 값 저장
        }
    }
    cout << result*result; //넓이 출력
}

입력부분이 한줄로 되어있기 때문에 문자열, 또는 문자로 입력받고 숫자로 변환하는 과정이 필요하다.

그리고 현재 위치를 기준으로 좌, 좌상, 상에 위치한 값들을 확인하여 최소값 + 1을 저장해준다.

이는 2x2 정사각형에 대한 체크이며 현재 위치를 제외한 모두의 값이 1이라면 2x2 정사각형이 성립한 것이기에 현재 위치에 2가 저장되게 된다.

 

3x3의 경우도 마찬가지다.

현재 값을 기준으로 좌, 좌상, 상 부분의 2x2 정사각형이 모두 존재한다는 것이기에 좌, 좌상, 상 부분의 최소값이 2일 것이다.

여기에 + 1을 했으므로 현재 위치에 3이 저장되게 된다.

최대값의 넓이를 출력하는 것이기에 해당 길이의 최대값을 따로 저장하여 제곱을 하여 출력해준다.

 

<현재 위치 : 오른쪽 아래>
1 0 
1 1
-> 좌 : 1, 좌상 : 1, 상 : 0 
-> 최소값 + 1 = 1
-> 정사각형 크기 1x1 (본인)

1 1
1 1
-> 좌 : 1, 좌상 : 1, 상 : 1
-> 최소값 + 1 = 2
-> 정사각형 크기 2x2

1 1 1
1 1 1
1 1 1
-> 직전 2x2 정사각형 계산으로 인해 2x2 정사각형의 오른쪽 아래 값들이 2로 변환

1 1 1
1 2 2
1 2 1
-> 좌 : 2, 좌상 : 2, 상 : 2
-> 최소값 + 1 = 3
-> 정사각형 크기 3x3

 2x2 정사각형의 크기를 판별하는 것은 쉽지만, 이후의 정사각형은 어떻게 판별해야 하나 애를 먹었던 문제이다.

따라서 검색의 도움을 빌렸는데 아직 DP의 점화식을 떠올리기는 쉽지 않은 것 같다.