[백준] 1915번 - 가장 큰 정사각형

www.acmicpc.net

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

문제

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

💡

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

시간 제한: 1초

메모리 제한: 128MB

입력

💡

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

출력

💡

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

예제 입력	예제 출력
4 4 0100 0111 1110 0010	4

풀이

배열을 입력받아 채운 뒤, 탐색으로 1을 찾았을 때 재귀를 통해 가능한 정사각형을 측정하고, 백트래킹을 이용해 확인한 배열은 넘어가도록 구현했는데 오답으로 나왔다. 다음으로 DP를 이용해 테이블의 각 원소를 사각형의 오른쪽 아래로 하는 가장 큰 사각형의 크기를 저장했다.

코드


#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    int n, m;
    vector<vector<int>> arr;
    vector<vector<int>> dp;
    cin >> n >> m;
    arr.resize(n, vector<int>(m));
    dp.resize(n, vector<int>(m, 0));
    // 배열 입력

    string input;
    for (int i = 0; i < n; ++i) {
        cin >> input;
        for (int j = 0; j < m; ++j) {
            arr[i][j] = input[j] - '0';
        }
    }

    int maxSize = 0;

    // DP를 이용한 최대 정사각형 크기 계산
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                }
                else {
                    dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
                }
                maxSize = max(maxSize, dp[i][j]);
            }
        }
    }

    // 최대 정사각형의 넓이 출력
    cout << (maxSize * maxSize) << endl;
    return 0;
}