4095

행렬안에서 1로 이루어진 최대 정사각형을 찾는문제.

가장 쉽게 생각한다면 모든 점에서 만들 수 있는 최대 정사각형을 탐색해보는 방법이 있지만 이럴경우 O(N^4)로 시간초과가 날 수 밖에 없다. 하지만 구하고자하는 사각형의 형태가 정사각형인점을 잘 이용하면 다이나믹 프로그래밍을 이용해 O(N^2)안에 해결 할 수 있다.

어떠한 위치에서 정사각형을 만들 때, 이전에 만들어진 정사각형의 정보를 활용할 수 있는 방법을 생각해보자.

4번(X, Y) 위치를 꼭지점으로 하는 정사각형을 만들려고하자. 그러면 4번위치 주위에 1, 2, 3번의 사각형들을 생각해볼 수 있다.

- 1번은 (X-1, Y-1)을 오른쪽 아래 꼭지점으로 할 때 가장 큰 정사각형이다.

- 2번은 4번에서 위로 그을 수 있는 최대 선분의 길이다.

- 3번은 4번에서 왼쪽으로 그을 수 있는 최대 선분의 길이다.

4번 위치를 꼭지점으로 하는 정사각형은 1, 2, 3번 사각형의 조합으로 만들어진다. 여기서 1, 2, 3번의 각각의 선분의 크기를 비교해가면서 다음과 같이 점화식을 정해줄 수 있다.

dp[x][y] = min(row[x][y], col[x][y], dp[x-1][y-1]+1)  

 
#include<stdio.h>
#define MAX 1001

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int dp[MAX][MAX];
int conti[MAX][MAX][2];	// row : 0, col : 1

int map[MAX][MAX];

int main() {
	int R, C;
	int i, j, ans;

	while (1) {
		scanf("%d %d", &R, &C);

		ans = 0;

		if (R == 0 && C == 0)
			break;

		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++) {
				scanf("%d", &map[i][j]);
				dp[i][j] = conti[i][j][0] = conti[i][j][1] = 0;
			}


		for (i = 1; i <= R; i++)
			for (j = 1; j <= C; j++) {
				if (!map[i][j])
					continue;
				conti[i][j][0] = conti[i - 1][j][0] + 1;
				conti[i][j][1] = conti[i][j - 1][1] + 1;

				dp[i][j] = MIN(dp[i - 1][j - 1] + 1, MIN(conti[i][j][0], conti[i][j][1]));

				if (dp[i][j] > ans)
					ans = dp[i][j];
			}

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

	return 0;
}