백준 1915번: 가장 큰 정사각형

[문제 링크]

1915번: 가장 큰 정사각형

---

top-down 방식으로 풀 경우 배열 (y,x)의 값이 1일 경우 가질 수 있는 가장 큰 정사각형 한 변의 길이는 →, ↓, ↘ 방향에 위치한 좌표에서 가질 수 있는 가장 큰 정사각형의 한 변의 길이 중 가장 작은값 + 1 이다. (y,x)의 값이 0일 경우는 정사각형이 만들어질 수 없기 때문에 변의 길이는 0 이다.

 

bottom-up 방식으로 풀 경우 채워나가는 방향이 반대이기 때문에 탐색 방향을 top-down과 반대로 하면 동일한 결과를 얻을 수 있다.

---

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

const int INF = 987654321;
int n, m, map[1001][1001], memo[1001][1001];

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int Topdown(int hereY, int hereX)
{
	int dy[3] = { 0,1,1 };
	int dx[3] = { 1,0,1 };

	if (hereY > n || hereX > m) return 0;
	if (map[hereY][hereX] == 0) return 0;

	int& ret = memo[hereY][hereX];
	if (ret != 0) return ret;

	ret = 1;

	int res = INF;
	for (int i = 0; i < 3; i++)
	{
		int next = Topdown(hereY + dy[i], hereX + dx[i]);
		res = min(res, next);
	}

	return ret += res;
}

int Bottomup()
{
	int dy[3] = { 0,-1,-1 };
	int dx[3] = { -1,0,-1 };

	int res = 0;
	for(int i=1; i<=n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 0)
				memo[i][j] = 0;
			else
			{
				int last = INF;
				for (int k = 0; k < 3; k++)
					last = min(last, memo[i + dy[k]][j + dx[k]]);

				memo[i][j] = map[i][j] + last;
			}
			res = max(res, memo[i][j]);
		}

	return res * res;
}

int main(void)
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		string str;
		cin >> str;
		for (int j = 1; j <= m; j++)
			map[i][j] = str[j - 1] - '0';
	}
	
	// top-down
	int res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			res = max(res, Topdown(i, j));
	cout << res * res << endl;
	
	// bottom-up
	cout << Bottomup() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 92 day