← All Articles

[BAEKJOON] 1915. 가장 큰 정사각형

Posted on

문제 :

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

image

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


입력 :

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


출력 :

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



풀이 :

꽤나 오래 전에 풀어본 기억이 나는 문제였는데, 당시에는 다이나믹 프로그래밍 방식으로 접근하는 것이 익숙치 않아서 전혀 감을 잡지 못했던 문제로 기억한다. 그래서 오늘 한번 풀어보자 생각하고 구현해보았다.

우선 가장 큰 정사각형의 넓이를 찾는 문제이기에 인덱스마다 얼마나 큰 정사각형이 있는지 모두 찾는 방법은 중복과정이 너무 많을 것 같았다. 때문에 DP 방식을 사용해야 할 것이라는 생각이 들었다. 그래서 생각해낸 방식은 그림으로 먼저 설명하자면,

image

가로, 세로 길이가 2인 작은 정사각형으로 모두 고려하면 문제가 편할 것 같았다. 위의 그림과 같이 최소값에 1씩 더해주면 현재 인덱스에서 가능한 최대 정사각형 한 변의 길이를 구할 수 있다. 때문에 마지막까지 메모이제이션을 실행해주면 전체 input 값의 최대 정사각형 값을 구할 수 있다.

알고리즘을 시작한 지 얼마 되지 않았을 때에는 DP로 접근 자체가 안되서 어려움이 있었으나 지금은 어느 정도 DP로 접근은 가능한 것 같다. 하지만 내 방식에도 여전히 중복된 연산 과정이 존재하기 때문에 더 최적화된 알고리즘을 생각해 볼 필요가 있다.



코드 :

코드 보기/접기 
#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
int ary[MAX][MAX];

int main() {
    int n, m, i, j, k, di[3] = { 0, 1, 1 }, dj[3] = { 1, 1, 0 }, cmpi, cmpj, minval, ans = 0;
    char num;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> num;
            ary[i][j] = num - '0';
        }
    for (i = n - 1; i >= 0; i--)
        for (j = m - 1; j >= 0; j--) {
            if (!ary[i][j]) continue;
            minval = 1111;
            for (k = 0; k < 3; k++) {
                cmpi = i + di[k];
                cmpj = j + dj[k];
                if (cmpi >= n || cmpj >= m || !ary[cmpi][cmpj]) break;
                minval = min(minval, ary[cmpi][cmpj]);
            }
            if (k >= 3) ary[i][j] = minval + 1;
            ans = max(ans, ary[i][j]);
        }
    cout << ans * ans << '\n';
}

AlgorithmalgorithmbaekjoonC++