[1915] 가장 큰 정사각형

문제 링크 : https://www.acmicpc.net/problem/1915

1915 - 가장 큰 정사각형

본문

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

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

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

입력

첫째 줄에 $n, m$ ($1 \leq n, m \leq 1\,000$)이 주어진다. 다음 $n$개의 줄에는 $m$개의 숫자로 배열이 주어진다.

출력

첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

dp로 해결할 수 있는 문제다. dp배열에는 문제에서 원하는 답인 “그 칸을 오른쪽 아래로 하는 가장 큰 정사각형의 크기” 로 설정한다. 그런 다음 LCS를 구하듯이 배열의 모든 칸을 탐색하며 dp를 해결한다.

dp의 점화식은 아래와 같이 설정하면 된다. \(dp[i][j] = \min{(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1}\)

• dp[i-1][j-1] : 정사각형의 대각선이 얼만큼 뻗어나갔는가?
• dp[i][j-1] : 정사각형의 가로선이 얼만큼 뻗어나갔는가?
• dp[i-1][j] : 정사각형의 세로선이 얼만큼 뻗어나갔는가?

현재 위치 $(i, j)$를 기준으로, 기준점을 오른쪽 끝 점으로 하는 정사각형을 확인하기 위해서는 3가지 방향을 확인하면 된다. 가로선, 세로선, 대각선. 그것을 확인할 수 있는 값으로는 앞서 얘기한 3개의 dp값이 되겠다. 각 dp값은, dp값의 뜻 자체가 “그만큼의 길이가 한 변인 정사각형이 거기 존재한다”의 의미이므로, 그만큼의 범위가 모두 1로 메워져있음을 알 수 있다.우리가 각 칸에서 할 일은, 3개의 변들 중 가장 짧은 것을 찾는 것이다. 그리고 그 값에 현재의 칸을 추가하여 기준점을 오른쪽 끝으로 하는 새로운 정사각형의 크기를 구할 수 있게 된다.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2024 / 3 / 5

#include <stdio.h>

#define MAX_IDX 1000

char grid[MAX_IDX][MAX_IDX + 1];
int dp[MAX_IDX][MAX_IDX];
int n, m;

int result;

#define min(a, b) (((a) > (b)) ? (b) : (a))
#define max(a, b) (((a) < (b)) ? (b) : (a))

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < m; ++j) {
            result = max(result, (grid[i][j] == '1'));
        }
    }

    for (int i = 0; i < m; ++i) {
        dp[0][i] = (grid[0][i] == '1');
    }
    for (int i = 0; i < n; ++i) {
        dp[i][0] = (grid[i][0] == '1');
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (grid[i][j] == '1') {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                result = max(result, dp[i][j]);
            }
        }
    }

    printf("%d", result * result);
    return 0;
}