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

구현

코드

#include<bits/stdc++.h>
#define MAX 1001
#define INF 0xFFFFFF
using namespace std;

int n, m;
string str;
int dp[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	int min_n = INF;
	int max_n = 0;
	for (int i = 1, a, b, c; i <= n; i++) {
		cin >> str;	// 띄어쓰기 없이 입력
		for (int j = 1; j <= m; j++) {
			dp[i][j] = str[j - 1] - '0';	// int로 삽입
			if (dp[i][j] == 0) continue;	// 1인 경우만 실행
			min_n = INF;
			a = dp[i - 1][j - 1];
			b = dp[i - 1][j];
			c = dp[i][j - 1];
			min_n = min(a, b);
			min_n = min(min_n, c);	
			dp[i][j] = min_n + 1;	// 최소값 + 1
			max_n = max(max_n, dp[i][j]);	// 가장 큰 정사각형의 변
		}
	}

	cout << max_n * max_n;	// 넓이

	return 0;
}