BOJ 15730(수영장 사장님) 풀이

이미지를 누르면 문제로 이동합니다

 

이 문제는 수영장이나 우물 관련 문제와 비슷한 스타일인 물을 담을 수 있는 영역의 크기를 구하는 문제이다. 

다른 문제들과는 다르게 N과 M의 범위가 크지 않기 때문에 다양한 풀이가 나올 수 있는데 이 글에선 Union Find를 이용하여 풀이를 작성하였다.

 

Union Find 를 어떻게 이용할 수 있을까?

Union Find(줄여서 유파)를 이용하기 전에 입력으로 주어진 환경에서 물이 어떻게 채워지는지 생각해 보자.

전체 영역에 물을 넣는다고 하면 가장 아래쪽에 공간이 있는 쪽부터 채워지며, 바깥쪽과 접촉하게 되기 직전까지 채워지게 된다.

 

입력 예제로 생각해 보면, 맨 처음에는 보이지는 않지만 안쪽 공간에 물이 채워지고, 다음에는 위 그림과 같이 물이 채워진다. 그 이후부터는 바깥쪽으로 흘러내려 채울 수 없게 된다.

여기서 우리는 이런 관찰을 할 수 있다.

 

격자에서 바깥쪽 좌표에 있는 곳에 물을 채울 때가 된다면 물이 흘러넘치지 않을까?

 

즉, 높이 h에 대해 바깥쪽 좌표에 해당하는 점이 h보다 같거나 작다면 그 점과 인접해 있는 h보다 작은 점들은 모두 물을 채울 수 없게 된다. 이를 이용하면 문제를 풀 수 있게 되며, 이때 n개의 점이 인접해 하나의 그룹을 이루고 있음을 구하기 위해 유파를 이용한다.

 

h는 0부터 최대 높이까지 진행하며, 현재 물을 채울 수 있는 좌표를 누적시키며, 결괏값에 더해줌으로써 문제를 해결할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
struct nd{
	ll x,y;
};
vector<nd>h[10010];
ll ans=0;
ll H[200][200];
ll parent[20000];
ll find(ll x){
	if(x==parent[x])return x;
	return parent[x]=find(parent[x]);
}
ll cnt[20000];
ll st[20000];
ll dy[4]={-1,0,1,0};
ll dx[4]={0,1,0,-1};
ll vmx=0;
void dfs(ll x,ll y){
	ll B=find(y*m+x+1);
	cnt[B]=0;
	for(int k=0;k<4;k++){
		ll nx=x+dx[k];
		ll ny=y+dy[k];
		if(nx<0 || nx>=m || ny<0 || ny>=n)continue;
		ll A=find(ny*m+nx+1);
		if(H[ny][nx]!=vmx && cnt[A]!=0){
			parent[A]=B;
			dfs(nx,ny);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	ll a;
	fill(cnt,cnt+20000,1);
	for(int i=0;i<20000;i++){
		parent[i]=i;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> H[i][j];
			vmx=max(vmx,H[i][j]);
			h[H[i][j]].push_back({j,i});
		}
	}
	ll v=0;
	for(int i=0;i<=vmx;i++){
		for(int j=0;j<h[i].size();j++){
			ll B=find(h[i][j].y*m+h[i][j].x+1);
			if(cnt[B]==0)continue;
			v++;
			for(int k=0;k<4;k++){
				ll nx=h[i][j].x+dx[k];
				ll ny=h[i][j].y+dy[k];
				if(nx<0 || nx>=m || ny<0 || ny>=n)continue;
				if(H[ny][nx]<=i){
					ll A=find(ny*m+nx+1);
					if(A==B)continue;
					parent[A]=B;
					cnt[B]+=cnt[A];
					if(cnt[A]==0){
						st[h[i][j].y*m+h[i][j].x+1]=1;
					}
					cnt[A]=0;
				}
			}
		}
		for(int j=0;j<h[i].size();j++){
			ll B=find(h[i][j].y*m+h[i][j].x+1);
			ll Y=h[i][j].y,X=h[i][j].x;
			if(st[h[i][j].y*m+h[i][j].x+1]==1 || Y==n-1 || Y==0 || X==m-1 || X==0){
				v-=cnt[B];
				cnt[B]=0;
			}
		}
		ans+=v;
	}
	cout << ans;

}