[백준] 4095번 : 최대 정사각형 (C++)

4095번 : 최대 정사각형

---

문제)

1과 0으로 이루어진 NxM크기의 행렬이 주어졌을 때, 1로만 이루어진 가장 큰 정사각형 부분 행렬 찾는 프로그램을 작성하시오. 

 

 

입력 :

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 개가 주어진다.

 

 

 

출력 :

각 테스트 케이스에 대해서 가장 큰 정사각형의 너비 또는 높이를 출력한다. 만약 그런 정사각형이 없을 때는 0을 출력한다.

 

 

 

 

 

 

풀이)

 

// 4095. 최대 정사각형
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
int ans = 0;
 
int dp[1002][1002];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    while (true)
    {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
 
        vec.clear();
        vec.resize(n + 1, vector<int>(m + 1, 0));
 
        fill(&dp[0][0], &dp[1001][1002], 0);
 
        // N x M 행렬 채우기 
        int a;
        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < m + 1; j++)
            {
                cin >> a;
                vec[i][j] = a;
            }
        }
 
        ans = 0;
        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < m + 1; j++)
            {
                if (!vec[i][j]) continue;
 
                vec[i][j] = min(vec[i - 1][j - 1], min(vec[i][j - 1], vec[i - 1][j])) + 1;
                ans = max(ans, vec[i][j]);
            }
        }
 
        cout << ans << '\n';
    }
 
    return 0;
}
 
 
 

 

 

---

출처 : https://www.acmicpc.net/problem/4095 

4095번: 최대 정사각형