[BOJ]백준 1915번: 가장 큰 정사각형/DP

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

1. 문제 정의

좌표 평면 내의 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다

이 때, 넓이를 구하기 위해 가장 큰 정사각형의 한 변의 길이를 구한다

위와 같은 그림에서 최대 정사각형의 한 변의 길이는 2이므로, 답은 4이다

 

2. Subproblem&Recursion

특정 좌표를 오른쪽아래 꼭지점으로 정사각형의 길이를 구한다고 할 때, 이 좌표의 북, 서, 북서쪽 좌표는 반드시 1이어야 한다.

 

그리고 좌표가 아래와 같을 경우,

0111001     ->        0111001 
0111001    ->         0122001 
0111100    ->         0123100 
0001101    ->         0001201

 

(X,Y)기준으로 (3,2)에 위치한 좌표의 최대 변 길이는 북서쪽의 최대 변 길이인 2에 1을 더한 것을 확인할 수 있다

따라서 (X,Y)의 최대 변 길이 = (X-1,Y-1)의 최대 변 길이+1로 생각할 수 있다.

 

하지만 (4,3)을 보면, (3,2)의 최대 변 길이는 3이지만, (3,3)과 (4,2)가 연결되어 있지 않기 때문에 (4,3)의 최대 변 길이는 2이다.

결과적으로 (X,Y)의 최대 변 길이 = min( (X-1,Y-1)의 최대 변 길이, (X-1,Y)의 최대 변 길이, (X,Y-1)의 최대 변길이 ) +1로 정할 수 있다

 

3. Memoization & Recurrence Relation

이차원 배열을 이용해서 DP의 중간 결과물을 저장한다.

 

Base case: 0행, 0열의 경우는 기존 array의 값을 그대로 가져온다. 기존 array의 값이 0인 경우에도 dp의 값은 0이다.

dp[y][x]를 구하기 위해서는 dp[y][x-1], dp[y-1][x], dp[y-1][x-1]을 미리 구해야 한다.

따라서 dp의 값은 이전의 열, 이전의 행에 dependent하므로 행->열의 오름차순으로 값을 구한다

 

4. Psudo code

1,2,3번에서 구한 점화식을 코드로 구현한다

 

5. C++ Code

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, arr[1001][1001], dp[1001][1001], ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
			if (!i || !j || !arr[i][j])
				dp[i][j] = arr[i][j];
			else if (arr[i - 1][j] && arr[i][j - 1] && arr[i - 1][j - 1]) {
				dp[i][j] = min({ dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] }) + 1;
			}
			else {
				dp[i][j] = 1;
			}

			if (dp[i][j] > ans)ans = dp[i][j];
		}
	printf("%d", ans * ans);
	return 0;
}

 

6. Time Complexity

N*M의 배열에 대해 1번씩 시행하므로 O(NM)내에 동작한다