BOJ [1915] 가장 큰 정사각형

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

1. 분류

다이나믹 프로그래밍

2. 풀이

0과 1로 이루어진 배열이 주어지고, 그 중 1로만 이루어진 가장 큰 정사각형의 넓이는 구하는 문제이다.

1051번 문제와 유사하나, 전부 1이어야 정사각형으로 인정한다는 점에서 다르다.

행열의 최대 크기는 1000x1000이고 하나하나 찾아가자면 O(N^3) 이상의 시간이 소요될 것으로 보이는데,

1000의 세제곱은 10억이므로 완전탐색은 불가능하다.

그렇다면 행열 요소를 하나하나 찾아가면서 정사각형의 크기를 바로 기록하는 방법은 없을까?

문제에서 주어진 정사각형의 내부는 모두 1이라는 성질을 생각해보니 DP로 이용할 점화식을 구할 수 있었다.

큰 정사각형은 내부에 작은 정사각형을 가지고 있다는 것을 생각해보자.

먼저 정사각형의 크기가 담길 부분의 기준을 정해야한다.

왼쪽 위부터 오른쪽 아래까지 차례차례 훑어가며 구할 것이기 때문에 정사각형의 오른쪽 아래에 크기를 담기로 하였다.

     

2x2 정사각형의 경우 오른쪽 아래에 담는 크기는 2가 된다.

3x3 이상의 크기부터는 조금 더 생각을 해 보자.

우선 아까와 같이 2x2 크기 정사각형의 크기를 먼저 담아본다면 이렇게 될 것이다.

우측 하단엔 3이 저장되어야 한다.

저장된 2들을 이용하여 1을 3으로 바꿔준다.

이러한 일련의 과정을 거치면 하나의 점화식을 도출해낼 수 있다.

[N, M] += MIN ( [N, M - 1], [N - 1, M], [N - 1 , M - 1] )

우측 하단에는 원래 있던 값에다 정사각형 배열 중 가장 작은 값을 더해주는 것이다.

여기에 하나의 조건을 더 고려하면 끝이다.

위의 조건대로라면 우측 하단은 0 + 1(최소값) = 1이 되어야 한다.

그러나 0이 들어간 이상 정사각형으로 인정할 수 없다.

반대로 정사각형 요소가 0이면 아무 문제가 없다.

1 + 0(최소값) = 1이기 때문이다.

대부분의 DP문제가 그러듯이 점화식만 구하면 소스코드는 쉽게 짤 수 있다.

3. 소스코드

#include <cstdio>

#define min(a, b, c) (a) > (b) ? ((b) > (c) ? (c) : (b)) : ((a) > (c) ? (c) : (a))
#define max(a, b) (a) > (b) ? (a) : (b)

int dp[1000][1000];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			scanf("%1d", &dp[i][j]);
	}

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

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			ans = max(ans, dp[i][j]);
	}

	printf("%d\n", ans * ans);

	return 0;
}