백준 #1915 가장 큰 정사각형

백준 #1915 가장 큰 정사각형

0과 1로 된 배열에서 1로 이루어진 가장 큰 정사각형의 크기를 구하는 문제.

배열 dp에 해당 좌표를 우측 하단으로 하는 가장 큰 정사각형의 한 변의 길이를 저장한다.

위, 왼쪽, 왼쪽 대각선 위의 세 좌표를 우측 하단으로 하는 가장 큰 정사각형의 한 변의 길이의 최솟값 + 1이 해당 좌표에서 가능한 가장 큰 정사각형의 한 변의 길이다.

문제는 정사각형의 크기를 출력하는 것이니 배열 dp의 최댓값을 제곱하여 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <bits/stdc++.h>
using namespace std;

int board[1000][1000];
int dp[1000][1000];

int calc(int x, int y) {
	if (dp[x][y] != -1) {
		return dp[x][y];
	}
	else {
		if (board[x][y] == 0) {
			dp[x][y] = 0;
		}
		else if (x == 0 || y == 0) {
			dp[x][y] = 1;
		}
		else {
			dp[x][y] = min({ calc(x - 1, y), calc(x, y - 1), calc(x - 1, y - 1) }) + 1;
		}
		return dp[x][y];
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	memset(board, 0, sizeof(int) * n * m);
	for (int i = 0; i < n; i++) {
		fill(dp[i], dp[i] + m, -1);
		string line;
		cin >> line;
		for (int j = 0; j < m; j++) {
			board[i][j] = (int)line[j] - '0';
		}
	}
	int maxEl = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			calc(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			maxEl = max(maxEl, dp[i][j]);
		}
	}
	cout << maxEl * maxEl;
	return 0;
}