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

문제: 가장 큰 정사각형 (백준 1915번)

문제 분석

주어진 $(N \times M)$ 크기의 이진 행렬(0과 1로 구성된)에서,
1로만 이루어진 정사각형 영역 중 가장 큰 정사각형의 넓이를 구하는 문제이다.
즉, 행렬에서 연속된 1들로 구성된 정사각형의 최대 넓이를 구하면 된다.

---

해결 방법: 동적 계획법 (DP)

문제를 효율적으로 풀기 위해 동적 계획법(DP)을 사용할 수 있다.
여기서 핵심 아이디어는,

• dp[i][j]를 (i, j)를 우측 하단 모서리로 하는 가장 큰 정사각형의 한 변의 길이로 정의하는 것이다.
• 설명:
  (i, j) 위치에서 정사각형을 확장하기 위해서는 바로 위, 왼쪽, 그리고 대각선 왼쪽 위의 위치에 있는 정사각형 크기가 모두 일정 이상이어야 한다.
  이 세 방향 중 가장 작은 값에 1을 더하면 (i, j)를 포함하는 정사각형의 최대 변의 길이가 된다.

• 만약 $v[i][j] = 0$이면 $dp[i][j]=0$
  • 해당 위치는 정사각형의 일부로 사용할 수 없으므로 0이다.

경계 조건:

• 행 또는 열의 첫 번째 원소들은 더 이상 확장할 수 없으므로,
  • $i=0$ 또는 $j=0$인 경우, $dp[i][j]=v[i][j]$ (입력 값에 따라 1 또는 0)

마지막에, 모든 $dp[i][j]$ 중 최대값을 찾고, 그 제곱을 출력하면 최대 정사각형의 넓이가 된다.

---

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    int n, m; 
    cin >> n >> m;
    
    // 입력 행렬: 문자형으로 입력받은 후, 각 자리의 숫자를 bool로 저장 (1은 true, 0은 false)
    vector<vector<bool>> v(n, vector<bool>(m));
    vector<vector<int>> dp(n, vector<int>(m));
    
    for (int i = 0; i < n; i++)
    {
        string s; 
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            int num = s[j] - '0';
            v[i][j] = num;  // 1이면 true, 0이면 false
        }
    }
    
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!v[i][j]) continue;  // 해당 위치가 0이면 건너뜀
            
            // 경계 조건: 첫 번째 행 또는 첫 번째 열이면, 해당 위치의 값이 정사각형의 최대 변의 길이가 됨.
            if (i == 0 || j == 0)
            {
                dp[i][j] = 1;
                answer = max(answer, dp[i][j]);
                continue;
            }
            // 점화식 적용: 위, 왼쪽, 대각선 왼쪽 위의 dp값 중 최소값 + 1
            dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
            answer = max(answer, dp[i][j]);
        }
    }
    
    // 최대 변의 길이의 제곱이 정사각형의 넓이가 됨.
    cout << answer * answer;
}