1915 가장 큰 정사각형 (동적계획법) [Gold IV]

1915번: 가장 큰 정사각형 (acmicpc.net)

 

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

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

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

 

 

풀이법

 

최대한 적은 양의 연산으로 안이 꽉 채워진 정사각형을 찾아야 합니다. 

여기서 핵심은 꽉 채워진 정사각형은 결국 작은 정사각형의 모임이라는 것 입니다. 

 

위의 3*3 정사각형 안에도 4개의 2*2 정사각형이 보이네요

마찬가지로 4 * 4 정사각형도 4개의 3 * 3 정사각형이 보이겠죠?

 

그럼 2 * 2 정사각형은 어떻게 정의 될까요?

왼쪽, 위, 대각선 방향의 인덱스에 1이 입력이 되어 있다면 2 * 2 정사각형 이라고 할 수 있겠습니다.

그럼 현재 index에 2라고 표시해 둘 수 있겠네요

 

3*3의 경우 왼쪽, 위, 대각선 방향의 인덱스 모두 2로 표시되어 있다면 3*3 정사각형,

4*4도 마찬가지 일 것 입니다.

 

예시

아래 입력 값으로 예시를 보여 드리겠습니다.

초기 값 입니다.

왼쪽, 위, 대각선 방향의 인덱스가 모두 1이니 2로 표시 했습니다.

 

위, 대각선 방향의 인덱스가 1이고 왼쪽은 2입니다.

결국 만들 수 있는 것은 2*2 정사각형이니 2로 표시합니다.

 

마찬가지로 2로 표시

 

왼쪽, 위, 대각선 방향의 인덱스가 모두 2이니 3로 표시 했습니다.

 

가장 큰 숫자가 3으로 나왔고

정사각형의 사이즈를 출력하니 3*3을 출력하면 끝 입니다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;
 
static int D[1001][1001];
static int A, B;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);
	 
	cin >> A >> B;
    
	int result = 0;
	for (int i = 1; i <= A; i++)
	{
		string t;
		cin >> t;

		for (int j = 1; j <= B; j++) 
		{
			D[i][j] = int(t[j -1] - '0'); 

			if (D[i][j] == 1) {
				D[i][j] = min(D[i - 1][j], min(D[i][j - 1], D[i - 1][j - 1])) + 1;  
			}
			result = max(result, D[i][j]);    
		}
	} 
	   
	cout << result * result; 
}