[BOJ 25761 // C++] 축사 건설

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25761번 문제인 축사 건설이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25761 

25761번: 축사 건설

0과 1로 이루어진 R행 C열 격자에서 0(또는 1)만으로 이루어진 가장 넓은 직사각형을 찾는 문제를 O(RC)으로 푸는 방법을 알고 있다면 쉽게 해결할 수 있는 문제이다.

 

구체적으로, 모든 토지영역은 밑변이 존재하므로, 각 행을 밑변으로 갖는 직사각형 영역들의 높이별 밑변의 길이의 최댓값을 구하는 것으로 문제를 해결할 수 있다. 이는 가로 길이가 C인 히스토그램 문제(6549번 문제)를 R번 실행하는 것과 유사한 과정으로 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int R, C, Q;
int height[2000];
int ans[2001];

stack<pair<int, int>> stk; // {높이, 길이}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		string s; cin >> s;
		stk.push(make_pair(-1, 1));

		for (int c = 0; c < C; c++) {
			int& cur = height[c];
			if (s[c] == '#') cur = 0;
			else cur++;
			int len = 0;
			while (stk.top().first >= cur) {
				len += stk.top().second;
				ans[len] = max(ans[len], stk.top().first);
				stk.pop();
			}
			stk.push(make_pair(cur, len + 1));
		}

		int len = 0;
		while (stk.top().first >= 0) {
			len += stk.top().second;
			ans[len] = max(ans[len], stk.top().first);
			stk.pop();
		}
	}

	for (int i = C - 1; i > 0; i--) {
		ans[i] = max(ans[i], ans[i + 1]);
	}

	cin >> Q;
	while (Q--) {
		int r, c; cin >> r >> c;
		if (r <= ans[c]) cout << "YES\n";
		else cout << "NO\n";
	}
}