baekjoon
[백준] 1915 가장 큰 정사각형
윤만석
2023. 4. 28. 11:34
문제
n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 |
0 | 0 | 1 | 0 |
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.
입력
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
출력
첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.
구조체(클래스)를 선언합니다.
r: 현재 노드기준 가로길이(왼쪽으로 1의 길이)
c: 현재 노드기준 세로길이(위쪽으로 1의 길이)
k:현재 노드기준 가장 큰 정사각형의 한변의 길이
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, INF = 987654321;
using namespace std;
class pos {
public:
int r = 0;
int c = 0;
int k = 0;
};
int N, M, mp[1001][1001], ans = 0;
char c;
pos dp[1001][1001];
int main() {
FAST;
cin >> N >> M;
REP(i, N) {
REP(j, M) {
cin >> c;
if (c == '1') {
dp[i][j].r = dp[i][j - 1].r + 1;
dp[i][j].c = dp[i - 1][j].c + 1;
dp[i][j].k = dp[i - 1][j - 1].k + 1;
dp[i][j].k = min(min(dp[i][j].r, dp[i][j].c), dp[i][j].k);
}
if (dp[i][j].k)ans = max(ans, dp[i][j].k);
}
}
cout << (int)pow(ans, 2);
}