[BaekJoon][1915] 가장 큰 정사각형

BAEKJOON ONLINE JUDGE

1915 가장 큰 정사각형

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

DP!!

풀이 1. 수학 + 구현

1000x1000 이므로 일단 input을 한번씩 탐색하는 것은 가능하다.

but, 탐색하면서 정사각형인지를 판단할 때 배열을 다시 탐색하는 일은 아마도 Time Limit이 발생할 것이다.

따라서, 정사각형인지를 판단하는 여부를 줄였다.

정사각형의 면적은 한 변의 제곱이다.

또한 입력은 0아니면 1이기 때문에 배열에 해당하는 값의 합(면적)이 한 변의 제곱과 같으면

정사각형이라고 판단하였다.

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

위 입력에서 표시한 지점의 입력의 합 4이며 변이 2인 정사각형의 면적과 같다.

면적을 구할 때 또한 반복문을 통해 일일이 계산을 하면 탐색이 중복된다.

따라서 효율적으로 합을 구하는 방법은

sum[i][j] 배열을 이용하는 것.

sum[i][j] 배열은 (0, 0)부터, (i, j)에 해당한는 지점까지의 합을 뜻한다.

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

예를 들어 위 입력에서 sum[2][1] = 4로 노란 지점의 합이다.

for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
        scanf("%1d", &map[i][j]);
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
    }
}

이렇게 각 지점의 (0, 0)부터의 면적을 구한 후

원하는 지점의 면적은 

space = sum[y][x] - sum[y][j] - sum[i][x] + sum[i][j];

식으로 구할 수 있다.

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

즉, 위 예제에서 하늘색에 해당하는 면적은 색이 칠해진 전체에서 노란색 부분을 빼고, 빨간색 부분을 빼고, 주황색 부분은 노란색과 빨간색을 빼줄 때 겹치는 부분으로 중복되어 빼지기 때문에 다시 더해주면 구할 수 있다.

따라서 면적을 구하는 방법은 반복문이 아닌 하나의 식으로 대체할 수 있다.

다음 단계로, 가장 큰 정사각형을 구해야 하기 때문에 한 지점 (y, x)를 정사각형의 왼쪽 위 좌표로 하였을 때

변수 length을 두어 그만큼의 sum과 길이 제곱을 통한 면적의 비교로 정사각형의 여부를 판단하고,

정사각형일 때 length++을 하여 더 큰 정사각형인지를 찾았다.

그 다음 (y, x)를 시작으로 길이 length인 정사각형의 최대치를 찾은 후에는 

y, x를 탐색해 가며 length보다 긴 길이를 가진 정사각형을 탐색한다.

설명이 장황하여 어렵지만... 어렵게 푼거 같다...

#include <stdio.h>
 
int map[1001][1001];
int sum[1001][1001];
int n, m;
 
int max(int first, int second) {
    if (first > second)    return first;
    return second;
}
 
int search()
{
    int y, x;
    int mx = 0;
    int length = 0, space;
 
    for (y = 1; y + length <= n; y++) {
        for (x = 1; x + length <= m; x++) {
            if (!map[y][x] || !map[y + length][x + length])    continue;
    
            space = sum[y + length][x + length] - sum[y - 1][x + length] 
                    - sum[y + length][x - 1] + sum[y - 1][x - 1];
 
            while (space == ((length + 1) * (length + 1))) {
                if (space > mx)    mx = space;
                length++;
                space = sum[y + length][x + length] - sum[y - 1][x + length]
                         - sum[y + length][x - 1] + sum[y - 1][x - 1];
            }
        }
    }
    
    return mx;
}
 
int main()
{
    int i, j;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            scanf("%1d", &map[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]
                            - sum[i - 1][j - 1] + map[i][j];
        }
    }
 
    printf("%d\n", search());
 
    return 0;
}

풀이 2.

그렇지만 DP로 풀면 간단하게 풀 수 있다.

#include <stdio.h>
 
int n, m;
int dp[1000][1000];
 
int min(int first, int second)
{
    if (first < second)    return first;
    return second;
}
 
int main()
{
    int i, j;
    int num;
    int max = 0;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            scanf("%1d", &num);
 
            if (i == 0 || j == 0)    dp[i][j] = num;
            else {
                if (num) {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    if (dp[i][j] > max)    max = dp[i][j];
                }
            }
        }
    }
 
    printf("%d\n", max * max);
 
    return 0;
}

input이 1일 때 지점의 왼쪽, 위, 왼쪽 위(대각선방향)을 보고 그 중 작은 수 + 1 을 통해 구해나갈 수 있다.

이는 정사각형의 오른쪽 아래를 point로 하여 만들 수 있는 정사각형의 변의 길이를 의미한다.

예를 들어 (위 입력과 다른 예)

0	1	0	0
1	1	1	1
0	1	2	2
0	1	2	3

같은 경우 dp[][]의 값인데, i = 0인 지점과 j = 0인 지점은 input과 같다.

그 이유는 위쪽과 왼쪽을 바라 볼 수 없기 때문에 입력과 같은 것이다.

(입력의 1과 달리 dp의 1은 정사각형 변의 길이 1을 의미)

왼쪽과 위, 왼쪽 위를 바라보았을 때 가장 작은 수가 0이면 dp[i][j] = 1이 된다.

이는 input이 그 중 0을 가지고 있기 때문에 그를 포함한 정사각형은 만들 수 없어서 

변의 길이가 1개인 정사각형만 만들 수 있음을 의미.

그리고 바라본 곳이 예를들어 2, 2, 2였을 때, dp[i][j] = 2 + 1이 되어 길이 3인 정사각형의 정사각형을 만들 수 있다.

2, 2, 2가 의미하는 것은 그로부터 길이 2인 정사각형이 존재한다는 것인데 이는 

포인트로부터 한 칸 위부터 길이 2, 한 칸 좌측부터 길이 2, 대각선 길이 2만큼 이미 사각형이 존재한다는 것이고

포인트에 위치한 곳을 더하면 3의 정사각형을 만들 수 있다는 것이다.