[BOJ] 1687 행렬 찾기

문제: https://www.acmicpc.net/problem/1687

 

 

문제 풀이:

'히스토그램에서 가장 큰 직사각형' 문제에서 스택을 사용한 풀이법을 이용하면 된다.

 

- func()함수: 현재 위치에서 위로 0의 개수(막대의 높이)를 기록

  [현재 위치에서 막대의 높이=자신의 위에 저장된 값+1]로 저장하면 된다. 

 

- 모든 높이에 대해 func2()함수를 돌려 최대 직사각형 크기를 찾는다

  func2() 함수는 '히스토그램에서 가장 큰 직사각형 문제 풀이와 동일하다

 

- 전체에서 가장 큰 크기를 찾을 것이기 때문에 ans는 맨 처음 0으로 초기화해주는 것을 제외하고는 초기화하지 않는다.

 

소스 코드:

#include <iostream>
using namespace std;

typedef long long ll;

int n, m;
int height[335][335];
char arr[335][335];
int ans;
struct stack {
	int first;
	int second;
};
stack st[335];

void func() {
	for (int j = 0; j < m; j++) {
		if (arr[0][j] == '0') height[0][j] = 1;
	}
	for (int j = 0; j < m; j++) {
		for (int i = 1; i < n; i++) {
			if (arr[i][j] == '0') height[i][j] = height[i - 1][j] + 1;
		}
	}
}
void func2(int startline) {
	int pos = n;
	int top = -1;
	for (int i = 0; i < m; i++) {
		int a = height[startline][i];
		if (top == -1) {
			top++;
			st[top].first = i;
			st[top].second = a;
		}
		else {
			if (st[top].second > a) {
				while (top >= 0 && st[top].second > a) {
					pos = st[top].first;
					int t = (i - st[top].first)*st[top].second;
					ans = ans < t ? t : ans;
					top--;
				}
				++top;
				st[top].first = pos;
				st[top].second = a;
			}
			else if (st[top].second == a) continue;
			else {
				top++;
				st[top].first = i;
				st[top].second = a;
			}
		}
	}
	for (int i = 0; i <= top; i++) {
		int t = (m - st[i].first)*st[i].second;
		ans = ans < t ? t : ans;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	func();
	for (int i = 0; i < n; i++) func2(i);
	cout << ans << '\n';
	return 0;
}