BOJ 10548 (BOB)

boj 10548

 

solved.ac 기준 platinum 5 문제이다. 하지만 이런 문제 유형을 처음 본 나로서는 정말 어려웠다..

COCI 공식 해답지를 보고 공부한 결과,

문제의 아이디어는 히스토그램의 최대 넓이를 구하는 문제를 스택을 사용한 스위핑 알고리즘으로 푸는 것과 비슷하다.

(BOJ 1725) 히스토그램 문제를 분할 정복으로 해결하면 $O(NlogN)$ 이 걸리지만 스위핑 알고리즘으로는 $O(N)$ 으로 충분하다.

마찬가지로 이번 문제도 $O(NM)$ 의 시간복잡도로 해결가능하다.

 

본 문제를 해결하는 기본 방법은 직사각형의 오른쪽 아래점을 고정 시켰을 때 몇 가지의 직사각형이 나올 수 있는지 구해서 모두 더하는 것이다.

$i$행에 대해서 위의 스위핑 알고리즘이 어떻게 적용되는지 알아보자.

$a[i][j]$: $(i,j)$의 숫자

$h[i][j]$: $(i,j)$부터 위로 얼마나 같은 숫자가 높게 있는지 그 높이

 

다음과 같이 스택에 $h[i][j]$=3,5,6이 있을 때 높이 4짜리 직사각형이 $(i,j)$에서 추가되었다고 생각해보자.

 

여기서 높이 4짜리가 추가되면서 증가하는 직사각형의 개수는 두 가지로 나눠서 계산할 수 있다.

$case1.$

위와 같이 (높이가 정확히 4짜리인) 파란색 직사각형의 내부에서 계산되는 직사각형 개수. 단, 시작점은 앞에서 언급했듯이 $(i,j)$가 고정이다. 즉, 전체 증가되는 개수는 $4\times3$. 여기서 3은 너비 3을 의미하는데, 높이가 4인 직사각형보다 높이가 크거나 같은 직사각형의 연속한 개수로 구할 수 있다.

따라서 높이가 5,6인 스택을 지우면서 새로 추가된 높이 4의 스택에 너비 3을 저장하면 다음에 구할 때 연속한 직사각형의 개수를 구하기 편할 것이다. 아래 코드에서 $suc$이 너비를 의미한다.

 

$case2.$

(그림에서 높이 5,6은 case1을 수행하면서 삭제된 상태이다) 

이번에는 높이 4보다 처음으로 작아지는 높이에  해당하는 스택으로부터 몇 개가 추가되는지 계산해야 한다.

당연히 이 경우는 높이가 3인 스택에서 추가된 직사각형의 개수만큼 늘어날 것이다.

즉, 스택을 추가함으로써 추가되는 직사각형의 개수를 그 스택의 정보에 저장하고 있으면 된다.

아래 코드에서 $num$이 바로 그 스택이 추가됨으로써 생겨난 직사각형의 개수를 의미한다.

 

더 자세한 내용은 코드를 보면서 이해하면 쉬울 것이다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<utility>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<cmath>
#include<time.h>
using namespace std;

/*coci 공식 해설 풀이*/
int n,m;
int a[1000][1000];
int h[1000][1000];
long long ans;
struct sq{
	int val,height,suc;
	long long num;
	sq(int v,int h,int s,long long n):val(v),height(h),suc(s),num(n){}
};

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	
	//(i,j)이 오른쪽 아래 점인 직사각형의 개수를 구한다.
	//느낌은 히스토그램 상의 최대 넓이 구하는 스위핑 알고리즘과 같은 방식이다
	for(int i=0;i<n;i++){
		stack<sq> st;
		st.push(sq(0,0,0,0));
		for(int j=0;j<m;j++){
			h[i][j]=1;
			if(i!=0 && a[i][j]==a[i-1][j]) h[i][j]=h[i-1][j]+1;
			//h[i][j] 높이를 가진 (i,j)에서 시작하는 최대 직사각형 안에서 셀수있는 직사각형의 개수
			int suc=1;
			while(st.top().val==a[i][j] && st.top().height>=h[i][j]){
				suc+=st.top().suc;
				st.pop();
			}
			long long res=suc*h[i][j];
			//그 외 h[i][j] 보다 높이가 작은 애들로부터 연장할 수 있는 직사각형 개수
			if(st.top().val==a[i][j]) res+=st.top().num;
			
			ans+=res;
			st.push(sq(a[i][j],h[i][j],suc,res));
		}
	}
	cout<<ans;	
	return 0;
}