1915번: 가장 큰 정사각형

문제 설명

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

[문제]

 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.

0	1	0	0
0	1	1	1
1	1	1	0
0	0	1	0

 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 

 

[입력]

 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.

 

[출력]

 첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.

 

[예제 입력 1]

4 4
0100
0111
1110
0010

[예제 출력 1]

4

---

풀이

 이 문제의 해결에 대한 전체적인 접근 방식은, 각 지점에서 특정 방향으로 연결된 1의 개수를 센 다음 이를 활용하여 정사각형의 크기를 구하는 방법이다.

 예제에 대해 풀이 방식을 적용해보자면, 우선 각 지점에서 자신의 오른쪽으로, 또 아래쪽으로 연결된 1의 개수를 세서 따로 보관하는 방법이다. 이를 적용해보면 2개의 벡터가 나오게 되는데, 자신의 오른쪽으로 몇 개의 1이 나와있는 지에 대한 벡터와,

0	1	0	0
0	3	2	1
3	2	1	0
0	0	1	0

자신의 아래쪽으로 몇 개의 1이 나와있는 지에 대한 벡터이다.

0	3	0	0
0	2	3	1
1	1	2	0
0	0	1	0

 그리고 두 벡터에서 각 지점의 최소값을 담은 새로운 벡터를 만들면, 이는 해당 지점에서 오른쪽과 아래쪽으로 1이 연속적으로 동일하게 얼마나 있는 지를 나타내는 벡터가 된다.

0	1	0	0
0	2	2	1
1	1	1	0
0	0	1	0

 그럼 이를 바탕으로 특정 지점에서 그려지는 최대 정사각형의 크기를 구할 수 있다. 예를 들어 3x3의 정사각형인 경우 해당 표 상에서는 그려지는 형태가 이렇게 된다.

3	?	?
?	2	?
?	?	1

 이렇게 우측 하단부터 왼쪽 대각선 형태로 올라가며, 값이 1부터 순차적으로 시작되고 이전 위치보다 값이 크기만 하다면, 현 위치에서 그려질 수 있는 최대 정사각형 크기는 이전 위치의 값 +1이 되는 것이다.

3	?	?	?
?	4	?	?
?	?	2	?
?	?	?	0

 이렇게 값이 나와도 여기서 그려질 수 있는 정사각형의 최대 크기는 3이 된다. 0부터 시작하여 왼쪽 대각선으로 올라가며 이전값보다 크기만하면 현 위치의 값을 +1 시키면 그 결과가 다음과 같기 때문이다.

3	?	?	?
?	2	?	?
?	?	1	?
?	?	?	0

 이러한 방식으로 2중 벡터의 맨 아래쪽과 오른쪽에서부터 왼쪽 대각선으로 거슬러 올라가며 앞선 예제의 벡터를 마저 최신화하면, 결과가 이렇게 나온다.

0	1	0	0
0	2	1	1
1	1	1	0
0	0	1	0

 그러고 전체 지점을 훑어, 각 지점의 최대값을 구하면 이는 전체 벡터에서 그려낼 수 있는 최대 크기 정사각형의 길이가 나오게 된다. 이를 제곱하여 반환하면 답이 나오는 방식이다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<vector<int>> arr;
	vector<vector<int>> result;
	int n, m;
	int answer = 0;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {//초기 필요한 벡터 초기화
		vector<int> temp(m, 0);
		vector<int> temp2(m, -1);
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			temp[j] = s[j] - '0';
		}
		arr.push_back(temp);
		result.push_back(temp2);
	}

	for (int i = 0; i < n; i++) {//오른쪽 방향 누적량 계산
		int count = 0;
		for (int j = m - 1; j >= 0; j--) {
			if (arr[i][j] == 1)
				result[i][j] = ++count;
			else
				result[i][j] = count = 0;
		}
	}

	for (int j = 0; j < m; j++) {//아래쪽 방향 누적량 계산
		int count = 0;
		for (int i = n - 1; i >= 0; i--) {
			if (arr[i][j] == 1)
				result[i][j] = min(result[i][j], ++count);
			else
				result[i][j] = count = 0;
		}
	}

	for (int i = 1; i < n; i++) {//배열의 오른쪽
		int row = i, col = m - 1;
		int dist = result[i][m - 1];
		while (--col >= 0 && --row >= 0) {
			if (result[row][col] > result[row + 1][col + 1])
				result[row][col] = result[row + 1][col + 1] + 1;
			else
				result[row][col] = result[row][col];
		}
	}

	for (int j = 1; j < m; j++) {//배열의 아래쪽
		int row = n - 1, col = j;
		int dist = result[n - 1][j];
		while (--col >= 0 && --row >= 0) {
			if (result[row][col] > result[row + 1][col + 1])
				result[row][col] = result[row + 1][col + 1] + 1;
			else
				result[row][col] = result[row][col];
		}
	}

	for (int i = 0; i < n; i++)//최대값 계산
		for (int j = 0; j < m; j++)
			answer = max(answer, result[i][j]);

	cout << answer * answer; //넓이 출력

	return 0;
}

---

결과