[알고리즘] C++ 백준 1915 가장 큰 정사각형

백준 1915

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

1915번: 가장 큰 정사각형

풀이 전 나의 생각

0과 1이 주어진 배열값을 판단하여 정사각형의 최대 크기를 구하는 문제다.

 

문제를 보면 뭔가 처음부터 계속 탐색을 하면서 값을 갱신 시켜야만 될 것 같다.

그럼 우선적으로 해야 할 것은 DP가 무엇을 의미하고 어떤 값을 갱신 시킬 지 알아야한다.

 

1. 조건을 보면 정사각형의 최대 크기를 구해야한다. 이 말은 직사각형이 아닌 정사각형을 구해야 하니깐 

한 변의 길이만 구하면 정사각형의 크기를 쉽게 구해낼 수 있다.

 

 2. DP는 이전 값을 참조하기 때문에 이전 값을 참조하며 정사각형의 조건을 모두 만족 시켜줄 수 있는

조건을 구해내야 한다.

 

3. 정사각형의 배열 값 중 0일 때는 무조건 정사각형이 되지 않기 때문에 0은 DP 탐색에서 제외해 줘야 한다.

 

그럼 결론은 정사각형 배열 값이 1일 때 참조할 수 있는 모든 위치에 최대의 한 변길이 값을 탐색하며 DP를

갱신해주면 된다.

 

 

문제 예시

 

여기서 정 중앙의 위치인 (1, 1) 을 기준으로 이전 값을 참조하며 정사각형의 조건을 만들어보자.

그럼 이전에 나왔던 값이면서 정사각형을 탐색할 수 있는 위치는 좌측 (1, 0), 좌측 대각선 (0, 0), 위 (0, 1)이다.

 

그럼 이를 통해 알 수 있는 점화식은 dp[i][j] = min({ dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j] }) + 1 이다.

이 점화식을 근거로 (1, 1)위치에서 나올 수 있는 한 변의 길이는 0 + 1 = 1이다.

즉, 지금 만들 수 있는 최대 크기의 정사각형은 1 * 1 = 1이다.

 

그럼 이제 알 수 있는 것은 어느 위치를 기준으로 좌측, 좌측 대각선, 위의 값에 1이 존재해야만 정사각형을 만들 수 있다는 것이다. 그럼 이 조건을 만족하는 (2, 2)위치에 가보자.

 

(2, 2)위치 기준으로 좌측, 좌측 대각선, 위의 값은 모두 1이다. 각 1들이 가질 수 있는 한 변의 길이의 최소값은 현재 1이기 때문에 (2, 2)위치에서 가질 수 있는 한 변의 길이는 1 + 1 = 2이다. 그럼 이 위치에서 얻을 수 있는 최대 정사각형의 크기는 

2 * 2 = 4 이다.

 

그럼 한 변의 길이가 2인 위치 값들이 어는 한 위치를 기준으로 좌측, 좌측 대각선, 위에 모두 존재한다면

한 변의 길이가 2 + 1 = 3이 되어 3 * 3 = 9인 정사각형을 만들어 낼 수 있다.

 

결론은 DP에서 갱신하는 한 변의 최소 길이 값이 주변에 1이 모두 있는지 없는지 판단해준다.

그렇기 때문에 이를 이용하여 정사각형의 최댓값을 쉽게 구해낼 수 있다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;
int square[1001][1001];
int dp[1001][1001];

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

	int n, m, MAX_length = 0;

	cin >> n >> m;

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

		for (int j = 1; j <= m; j++)
		{
			square[i][j] = num[j - 1] - '0';
		}
	}


	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (square[i][j] == 1) 
			{
				dp[i][j] = min({ dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j] }) + 1;
				MAX_length = max(MAX_length, dp[i][j]);
			}
		}
	}

	cout << MAX_length * MAX_length;
}