[ 백준 1915 ] 가장 큰 정사각형 (C++)

백준의 가장 큰 정사각형(1915) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 맵에서, 가장 큰 정사각형의 넓이를 출력하는 문제이다. Dynamic Programming으로 어떻게 구현해야 하는지

   알아보자.

   일단, 점화식부터 알아보고, 이후에 이해해보도록 하자.

   MAP[i][j] = Min(MAP[i - 1][j - 1] , Min(MAP[i - 1][j], MAP[i][j - 1])) + 1 

   점화식은 위와 같다.                                         

   왜 저런식이 도출되는지 알아보자. MAP[][] 2차원 배열은 우리가 입력할 때 입력받은 MAP을 저장하는 배열이다.

   MAP에는 1과 0으로 이루어져 있고 ,우리는 1로 이루어진 가장 큰 정사각형을 찾아야한다.

  

    위와 같은 맵이 있다고 생각해보자. 먼저, 정사각형인지 아닌지 어떻게 판단을 해야하는지부터 알아보자.

    본인은 모든 좌표를 돌면서, '1'인 지점에 대해서만 위의 점화식을 대입시켜 주었다.

    만약에, 모든 좌표를 도는 중, 어떤 한 좌표가 '0'이라고 생각해보자. 그 좌표를 기준으로 어떻게 보더라도, 정사각형이

    나올 수가 없다. 왜냐하면 그 좌표가 애초에 0이기 때문이다. 따라서 0인 좌표에 대해서는 계산을 해줄 필요가 없다.

    그렇다면 0이 아닌 경우에는 무슨 계산을 해줘야 할까??

    본인은 해당좌표를 기준으로 왼쪽 , 왼쪽 대각선 위 , 위 이렇게 3칸을 비교해보았다. 3칸을 비교하면서, 가장 작은 값에다가

    +1을 해주었다.

    위의 그림에서 (1, 1) 에 있는 '1'을 주목해보자.

    (1, 1)을 기준으로 왼쪽, 왼쪽 대각선 위, 위 이렇게 3개의 값은 { 0, 0, 1 } 이다. 이 때, 가장 작은 값은 0이고 + 1을 하면 1이 된다.

    즉, (1, 1)에서 나올 수 있는 최대 정사각형의 한변의 길이는 '1' 이라는 것이다.

    그렇다면, (2, 2) 좌표를 한번 봐보자. (2, 2)에서는 { 1, 1, 1 } 중에서 가장 작은 값인 1에 + 1을 한 2가 된다.

    즉 이 좌표에서는, 최대 정사각형의 한변의 길이는 2가 된다는 것을 의미한다.

    따라서, 0이 아닌 지점에 대해서 위의 점화식을 계산해주고, 최대길이를 계속해서 갱신해 주면 문제를 해결할 수 있다.

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j + 1] = Inp[j] - '0';
        }
    }
}
 
void Solution()
{
    int Max_Len = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (MAP[i][j] != 0)
            {
                MAP[i][j] = Min(MAP[i - 1][j - 1], Min(MAP[i - 1][j], MAP[i][j - 1])) + 1;
                if (Max_Len < MAP[i][j]) Max_Len = MAP[i][j];
            }
        }
    }
 
    cout << Max_Len * Max_Len << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}