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

다이나믹 프로그래밍 문제입니다.

n*n배열에서 가장 큰 정사각형의 넓이를 구하는 문제입니다.

첫번째로 입력받은 숫자를 
map[i][j] = s[j - 1] - '0';
통해서 하나씩 나누어서 배열에 넣었습니다.

두번째로 for문을 통해서 순차적으로 검색합니다.

1) 현재 위치가 0이면 continue;

2) 현재 위치가 0이 아니면
  (1) 왼쪽, 위쪽 왼쪽 위 대각선 중 하나라도 0이면 다음 배열 확인
  (2) 전부 0이 아니면 가장 작은 숫자에서 +1 한 값을 현재에 대입

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

int n, m;
int map[1010][1010];
int moveX[3] = { -1, 0, -1 };
int moveY[3] = { 0, -1, -1 };

int main(int argc, char *argv[])
{
	string s;
	cin >> n;
	cin >> m;


	memset(map, 0, sizeof(map));
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		for (int j = 1; j <= m; ++j) {
			map[i][j] = s[j - 1] - '0';
		}
	}

	int minNum;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			minNum = 1010;

			if (map[i][j] == 0) {
				continue;
			}

			for (int k = 0; k < 3; ++k) {
				int x = i + moveX[k];
				int y = j + moveY[k];

				minNum = min(minNum, map[x][y]);
				if (map[x][y] == 0) {
					break;
				}
				
				if (k == 2) {
					map[i][j] = minNum + 1;
					break;
				}
			}
		}
	}

	int maxNum = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			maxNum = max(maxNum, map[i][j]);
		}
	}
	cout << maxNum * maxNum << endl;

	return 0;
}