[BOJ] 1915 : 가장 큰 정사각형 - travelbeeee

문제 : https://www.acmicpc.net/problem/1915

---

[알고리즘풀이]

DP를 이용한 문제입니다.

다음과 같이 처음 dp[i][j] 에서 dp[i -1][j -1] / dp[i -1][j] / dp[i][j - 1] 이 0이 아니라 정사각형이 만들어지면 현재 만들어진 정사각형의 최대 길이를 dp[i][j]에 저장합니다.

3 x 3 크기의 정사각형은 다음과 같이 배열에 저장합니다.

물론, 한 곳이라도 0인 곳이 있으면 정사각형이 만들어지지 않으므로, 배열에 저장하지 않고 진행한다.

끝까지 진행해서 지금까지 만들어진 정사각형의 길이 중 가장 큰 값을 제곱해서 넓이를 출력한다.

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int map[1000][1000] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string input;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> input;
		for (int j = 0; j < m; j++)
			map[i][j] = int(input[j] - '0');
	}
	
	int ans = 0;
	for (int j = 0; j < m; j++)
		ans = max(ans, map[0][j]);
	for (int i = 0; i < n; i++)
		ans = max(ans, map[i][0]);

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			int t = min(map[i - 1][j - 1], min(map[i - 1][j], map[i][j - 1]));
			if (t > 0 && map[i][j] > 0)
				map[i][j] = t + 1;

			ans = max(ans, map[i][j]);
		}
	}

	cout << ans * ans;

}

---