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

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

1915번: 가장 큰 정사각형

 

2차원 배열 cache에, cache[x][y] = x, y가 오른쪽 아래인 정사각형의 한 변의 길이를 저장하여, 문제를 해결했다.

먼저 정사각형의 한 변의 길이가 1인 것을 DP 테이블에 채우고, 이를 이용해 bottom-up 방식으로 DP 테이블을 채워 나갔다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
int cache[1005][1005]; //[x][y] = x,y가 오른쪽 아래인 정사각형의 최대 한변의 길이
vector<string> board;

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;
		board.push_back(input);
	}

	//정사각형의 크기가 1인것을 dp에 먼저 채운다
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cache[i][j] = board[i][j] - '0';
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (board[i][j] == '1') { //(i,j)를 오른쪽 아래로 정사각형을 만들 수 있을때

				//더 큰 정사각형을 만들 수 없을때
				if (cache[i][j - 1] == 0 || cache[i - 1][j] == 0) {
					continue;
				}

				if (cache[i][j - 1] != cache[i - 1][j]) {
					int min_len = min(cache[i][j - 1], cache[i - 1][j]);
					cache[i][j] = min_len + 1;
				}

				else {
					if (cache[i - 1][j - 1] >= cache[i][j - 1]) {
						cache[i][j] = cache[i][j - 1] + 1;
					}
					else {
						cache[i][j] = cache[i][j - 1];
					}

				}
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			result = max(result, cache[i][j] * cache[i][j]);
		}
	}
	cout << result;

	return 0;
}