가장 큰 정사각형 C++

가장 큰 정사각형 문제 바로가기

이번 문제의 알고리즘은 DP를 사용해서 풀었습니다.

답안이 생각나지 않아, https://yabmoons.tistory.com/158 해당 글을 참고하여 풀었습니다.

처음 로직을 생각한건

x=1,y=1에 왔을때, 이중 포문을 map끝까지 돌면서 1인지 검사하여서 가장 큰 사각형을 찾는 로직을 생각했는데
이는 만약 모든 정사각형이 1로 채워져 있다면
100010001000*1000 이므로 1000000000000 이므로 무조건 시간 초과가 날것이라고 생각했습니다.

딱봐도 뭔가 DP로 풀어야할것 같긴한데, DP는 이전의 결과를 저장해 뒀다가, 다음에 써먹어야하는데 어떤 이전의 결과를 저장해 둘건지 생각이 나질 않았습니다.

우선 해당 사각형에서 끝에 있는 1이 왜 2*2 큰 사각형이 되지 못할까요?

당연히 왼쪽, 위쪽, 왼쪽 대각선의 3가지 블럭이 1이 아니기 때문입니다.

고로 2*2 사각형이 되려면 기준점이 1,1 배열의 원소라면
1,0 0,0 0,1 에 1이 있어야합니다.

그러면 3*3은 어떨까요?

3 곱하기 3 배열에서 마지막 빨간색 원소를 기준으로 3칸짜리 사각형이 되려면, 2칸짜리 사각형이 3개가 있어야합니다.

이러한 점들을 고려하여
2 * 2행렬로 가보면 아까 1로 전부 채워진 행렬에서 마지막 끝점을 기준으로

[i-1][j] [i][j-1] [i-1][j-1]의 배열에서 가장 작은 값을 가져와서 +1을 해줍니다.
만약 여기서 0이 하나라도 있다면 1이므로 마지막 끝 기준점의 원소배열의 값이 2가 아니라 1일것입니다.

해당 로직을 적용하면 3 * 3은 이렇게 됩니다.

그리고 조건을 생각해보면 숫자가 0이면 무조건 어차피 사각형이 안만들어지므로, 건너뛰고 1이면 검사를 하고

map을 map[0][0]부터 쭉 값을 넣고, 왼쪽 윗쪽, 대각만 확인하는거니까
for문을 1,1부터 돌리면 되는거 아닌가? 싶은데 그러면 안되는게

000000000
000000000
100000000
000000000...
이런식이면 1,1부터 검사를 하면 무조건 다 0이라 정답이 0으로 나오고 3,1에 있는 1을 계산을 못하게 된다.

고로, map을 초기화 할때 1,1부터 넣어서 계산을 하도록 해야한다.

#include <iostream>
#include <vector>

using namespace std;

int map[1010][1010];

int main() {
	int n = 0;
	int m = 0;

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		string s = "";
		cin >> s;
		for (int j = 0; j <= s.size(); j++) {
			map[i][j+1] = s[j] - '0';
		}

	}

	int answer = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 1) {
				int tmp = 2000;
				if (map[i - 1][j - 1] < tmp) tmp = map[i - 1][j - 1];
				if (map[i][j - 1] < tmp) tmp = map[i][j - 1];
				if (map[i - 1][j] < tmp) tmp = map[i - 1][j];

				map[i][j] = tmp + 1;
				if (tmp + 1 > answer) answer = tmp + 1;
			}
		}
	}

	cout << answer * answer << endl;
	return 0;
}