백준 1915: 가장 큰 정사각형

문제 요약

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

문제 분류

• 다이나믹 프로그래밍

문제 풀이

가장 큰 정사각형의 넓이를 구하라는 말은 곧 가장 긴 변의 길이를 구하라는 말과 같다. 이에 dp[i][j]에 대해 (i, j)를 정사각형의 오른쪽 아래 점으로 하는 가장 긴 정사각형 변의 길이로 정의하였다.
정사각형을 만드는 과정을 dp로 설계해보자. 어떤 ary[i][j]가 1이라면, [i-1][j], [i][j-1],[i-1][j-1]을 살펴보아, 그것들이 1이라면 최종 변의 길이는 2가 된다. 즉, 주변의 정사각형 길이의 최솟값 + 1이 되는 것이다.

즉, 점화식은 dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;이 되겠다.

0번 행과 열을 초기화해주면서 res도 갱신시켜주었고, dp를 탐색하면서 역시 res를 갱신시켜주어 res의 제곱을 출력하였다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int n, m, ary[1000][1000], res;
int dp[1000][1000];

int sol(int r, int c)
{
	if (!r || !c) {
		res = max(res, (ary[r][c]));
		return ary[r][c];
	}
	if (dp[r][c] > -1) return dp[r][c];
	dp[r][c] = min(min(sol(r - 1, c), sol(r, c - 1)), sol(r - 1, c - 1)) + 1;
	if (!ary[r][c]) dp[r][c] = 0;
	res = max(res, dp[r][c]);
	return dp[r][c];
}

int main() {
	string in;
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> in;
		for (int j = 0; j < m; j++)
			ary[i][j] = in[j] - '0';
	}
	
	sol(n - 1, m - 1);

	cout << res * res;
}