백준 1915 - 가장 큰 정사각형

www.acmicpc.net/problem/1915

 

2차원 배열에서 가장 큰 정사각형을 찾는 문제이다.

 

이 문제는 현재 위치에 정사각형이 존재할 경우(값이 1일 경우) 왼쪽, 위쪽, 왼쪽 위에 있는 원소의 최솟값을 더해 현재 인덱스까지의 가장 큰 정사각형의 길이를 저장할 수 있다.

 

예제를 통해 알아보자.

 

 

인덱스 (0, 0)처럼 왼쪽, 위쪽, 왼쪽 위의 원소를 볼 수 없거나 그 값이 0인 경우는 넘어간다.

 

 

인덱스 (1, 1)에서 왼쪽, 위쪽, 왼쪽 위를 살펴보면 위쪽의 값은 1이지만 그 외 값들은 전부 0이다.

세 원소의 최솟값이 0이므로 해당 인덱스까지 계산했을 때 정사각형의 최대 길이는 역시 1 + 0 = 1이다. 마찬가지로 인덱스 (1, 2), (1, 3), (2, 1)까지 계산했을 때 최대 정사각형의 길이는 1이 된다. 인덱스 (2, 2)로 넘어가 보자.

 

인덱스 (2, 2)를 둘러싼 세 원소가 전부 1임을 확인할 수 있다. 세 원소의 최솟값은 1이 되고

이를 현재 인덱스에 더하면

 

2가 되고 인덱스 (2, 2)까지 계산했을 때 가장 큰 정사각형의 길이는 2가 된다.

 

이렇게 배열에 대해 반복문을 돌면서 현재 인덱스까지 계산했을 때 가장 큰 정사각형의 길이를 구하고 그 값을 저장해나가면 전체 배열에서 가장 큰 정사각형의 길이를 구할 수 있다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int ar[1001][1001];
int r, c;

int line;

int main()
{
    ios::sync_with_stdio(false);
    
    (cin >> r >> c).get();
    
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= c; ++j)
            ar[i][j] = cin.get() - '0';
        cin.get();
    }
    
    for (int k = 1; k <= r; ++k)
    {
        for (int s = 1; s <= c; ++s)
        {
            if (!ar[k][s])
                continue;
            int seed = ar[k - 1][s];
            seed = min(seed, ar[k - 1][s - 1]);
            seed = min(seed, ar[k][s - 1]);

            ar[k][s] = 1 + seed;
            line = max(line, ar[k][s]);
        }
    }
    
    cout << line * line;
}

코드의 구현에서는 배열의 크기를 한칸씩 더 크게잡고 시작은 (1, 1)로 하여 인덱스가 넘어가는 일이 없도록 했다.