백준 1915 - 가장 큰 정사각형

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 주어진 2차원 배열에서 1로 만들 수 있는 최대 정사각형의 크기를 구하면 된다.

 

해당 문제는 완전 탐색에서 점차 발전시키면 간단하게 풀 수 있다.

우선 완전 탐색으로 정답을 구하기 위해서는 모든 칸에서 시작하여 그릴 수 있을 만큼 정사각형을 그려보면 된다.

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

이러한 입력이 있다고 가정해 보자.

그럼 (0 ,0)은 0이기 때문에 정사각형을 그릴 수 없다.

즉, 1인 칸만 확인하면 된다.

(0, 1)은 1이기 때문에 정사각형을 그려볼 수 있다.

우선 크기가 1인 정사각형을 그릴 수 있다.

이후 크기가 2인 정사각형을 그리려 했을 때 오른쪽 칸이 0이기 때문에 크기가 2인 정사각형은 그리지 못한다.

따라서 현재까지 그릴 수 있는 최대 정사각형은 크기가 1이다.

(1, 1)에도 동일한 방법을 통해 정사각형을 그렸을 때 최대 크기가 4인 정사각형을 그릴 수 있다.

정사각형을 그릴 수 있는지 판단하는 방법은 정해진 크기가 모두 1인지 확인하는 것이다.

하지만 이렇게 모든 칸을 다 더해보면 시간 초과가 발생할 것이다.

그렇기 때문에 정사각형을 그릴 수 있는지 여부를 빠르게 확인하는 방법이 필요하다.

 

정사각형을 그릴 수 있는 여부는 정해진 크기를 모두 더하는 것이다.

즉, 누적합을 이용하면 효율적으로 개선할 수 있다.

2차원 누적합을 통해 현재 탐색 지점을 기준으로 한 변의 길이가 x인 정사각형을 그린다 했을 때 다음과 같은 식으로 계산할 수 있다.

bool Check(int i, int j)
{
    int next = ans + 1;
    if (i + ans > N || j + ans > M) return false;
    return next * next == sum[i + ans][j + ans] - sum[i - 1][j + ans] - sum[i + ans][j - 1] + sum[i - 1][j - 1];
}

이때 ans는 현재 알고 있는 최대 크기의 정사각형의 한 변의 길이이다.

즉, 이미 찾은 최대 크기 이전은 검사하지 않도록 하는 것이다.

이것을 이제 모든 칸에서 진행하면 된다.

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        if (grid[i][j] == '0') continue;

        while (Check(i + 1, j + 1))
        {
            ans++;
        }
    }
}

 

그리고 누적합을 구하는 방법은 다음과 같다.

//가로
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= M; j++)
    {
        sum[i][j] = sum[i][j - 1] + (grid[i-1][j-1] - '0');
    }
}

//세로
for (int j = 1; j <= M; j++)
{
    for (int i = 1; i <= N; i++)
    {
        sum[i][j] += sum[i - 1][j];
    }
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N, M;
vector<string> grid;
vector<vector<int>> sum;
int ans = 0;

bool Check(int i, int j)
{
    int next = ans + 1;
    if (i + ans > N || j + ans > M) return false;
    return next * next == sum[i + ans][j + ans] - sum[i - 1][j + ans] - sum[i + ans][j - 1] + sum[i - 1][j - 1];
}

int main()
{
    INPUT_OPTIMIZE;

    cin >> N >> M;
    grid.resize(N);
    sum.resize(N + 1, vector<int>(M + 1, 0));

    for (int i = 0; i < N; i++)
    {
        cin >> grid[i];
    }

    //가로
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            sum[i][j] = sum[i][j - 1] + (grid[i-1][j-1] - '0');
        }
    }

    //세로
    for (int j = 1; j <= M; j++)
    {
        for (int i = 1; i <= N; i++)
        {
            sum[i][j] += sum[i - 1][j];
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == '0') continue;

            while (Check(i + 1, j + 1))
            {
                ans++;
            }
        }
    }

    cout << ans * ans;

    return 0;
}

---