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);
}