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

문제

백준 1915

1915번: 가장 큰 정사각형

풀이

해당 영역에서 가장 큰 길이를 계산해 담고 있는 dp 배열을 이용합니다.

먼저 0열과 0행에는 입력값과 똑같은 값을 넣어줍니다.

0열과 0행을 제외하고, 해당 칸의 입력이 0이라면, 어짜피 사각형의 길이는 0이 되므로 dp에 0을 넣어줍니다.

1이라면 왼쪽, 위쪽, 왼쪽 위 3가지 값을 탐색하면서 dp 값을 구합니다.

dp값과 최대 길이 값을 비교하여 최댓값을 갱신합니다.

 

예제를 보겠습니다.

square

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

dp

0	1	0	0
0
1			0
0	0		0

0행과 0열, 입력이 0인 부분은 square와 똑같이 초기화 합니다.

0	1	0	0
0	1	1	1
1	1	2	0
0	0	1	0

입력이 1인 부분은 (왼쪽, 위쪽, 왼쪽 위)의 최솟값에 1을 더한 값입니다. dp 배열을 채워줍니다.

가장 큰 사각형의 길이가 2입니다. 4를 출력합니다.

소스 코드

 

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int square[1000][1000];
int dp[1000][1000];
int n, m;
int main()
{
    int maxlength = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++)
        {
            char temp = s[j];
            square[i][j] = temp - '0';
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            dp[i][j] = square[i][j];
            int size = dp[i][j];
            if (square[i][j] == 1 && i != 0 && j != 0)
            {
                // 왼쪽과 위쪽 비교
                size = min(dp[i - 1][j], dp[i][j - 1]);
                // 대각선 왼쪽위 비교
                size = min(dp[i - 1][j - 1], size);
                size++;
                dp[i][j] = size;
            }
            // 최댓값 비교
            maxlength = max(size, maxlength);
        }
    }
    // 넓이
    cout << maxlength * maxlength;
    return 0;
}