[BOJ/백준 1915/C++] 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

 

[문제 요약]

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

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

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

 

[문제 조건]

- 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다.

- 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

2차원 배열에서 정사각형을 찾는건 그리 어렵지 않다. 1x1, 2x2, 3x3... 짜리 정사각형들은 모조리 찾아 보는 방법이 존재하긴 한다.

 

하지만 모두 찾는 방법은 시간이 매우 아주 엄청 오래 걸린다.

 

따라서 필자는 DP를 이용하여 이 문제를 해결하였다.

 

아이디어는 다음과 같다. 

 

2차원 배열을 하나씩 확인하면서 진행하는데 일단은 값이 0인 곳은 그냥 continue로 넘겨 주도록한다. 왜냐하면 우리가 하려는 것은 그 값을 포함하는 정사각형을 찾을 것인데 값이 0이면 그 값을 포함하는 정사각형은 무슨 짓을 해도 만들 수가 없다.

 

그렇다면 값이 1인 곳에서 정사각형을 찾아야 하는데 원리는 예제를 통해 확인해보자.

 

아래와 같은 예제가 있을 때 이 배열의 값들을 바꿀 것이다.

먼저, 첫 번째 행과 첫 번째 열은 뭔 짓을 해도 크기가 1x1짜리 정사각형만 나오기 때문에 탐색하지 않고 그대로 둔다.

그 다음 두 번째 부터 확인하게 되는데 다음과 같은 점화식을 이용한다.

 

DP[i][j] = i번째 행 j번째 값을 추가했을 때 얻을 수 있는 가장 큰 정사각형의 한 변의 길이

DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1이 된다. 단, 비교하는 3개의 값이 모두 0이 아니여야 한다.

 

이유를 한번 알아보자.

 

비교하는 값들이 나타는 사각형을 각각 색을 칠해보면

위 그림과 같이 나타낼 수 있다.

 

비교하는 값들이 전부 1이상이기 때문에 최소한 2x2의 정사각형이 나올 것이다.

 

DP[i-1][j]와 DP[i][j-1]의 값 중 작은 값에 의해 가질 수 있는 정사각형의 한 변의 길이가 나오고, 둘 중 작은 값과 DP[i-1][j-1]을 한 번 더 비교하여 현재 위치에서 가질 수 있는 정사각형 한 변의 길이의 하한선이 나온다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>

using namespace std;

int n, m;
vector<vector<int>> dp;
vector<vector<int>> mp;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	mp.resize(n);
	dp.resize(n);
	int ans = 0;
	for (int i = 0; i < n; i++) mp[i].resize(m);
	for (int i = 0; i < n; i++)
	{
		string tmp;
		cin >> tmp;
		for (int j = 0; j < m; j++)
		{
			mp[i][j] = tmp.at(j) - '0';
			ans = max(ans, mp[i][j]);
		}
	}
	
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < m; j++)
		{
			if (mp[i][j] == 0) mp[i][j] = 0;
			else
			{
				if (mp[i - 1][j] == 0 || mp[i][j - 1] == 0 || mp[i - 1][j - 1] == 0) continue;

				mp[i][j] = min(min(mp[i - 1][j], mp[i][j - 1]), mp[i - 1][j - 1]) + 1;			
			}
			ans = max(ans, mp[i][j]);
		}
	}

	cout << ans * ans; 
}

주의 할 점은 DP값이 의미하는게 한 변의 길이기 때문에 정답을 출력할때 제곱해서 출력해야 넓이가 나온다.

굳