[백준] 1113 수영장 만들기

문제

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661
61116
16661

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

어느 한 지점에 물을 부을 수 있을때, 그 지점을 물을 더이상 부을 수 없을 때 까지 붓게 만듭니다.

만약 어느 한 지점을 기준으로 상하좌우에 낮은 지점이 있다면 물을 부을 수 없습니다.

그 지점을 기준으로 같은 높이에있는 지점들에대해 탐색하면서 가장 높이 물을 부을 수 있는 높이까지 붓습니다.

반복합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int N, M, mp[51][51];
int bfs(int a, int b) {
	queue<pi>q;
	q.push({ a,b });
	int vis[51][51];
	mset(vis);
	vis[a][b] = 1;
	int mf = INT_MAX;
	int cnt = 1;
	vector<pi>temp;
	temp.push_back({ a,b });
	while (!q.empty()) {
		auto [y, x] = q.front();
		q.pop();
		rep(i, 4) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny > N || ny<1 || nx>M || nx < 1 || mp[ny][nx] < mp[y][x])return 0;
				if (mp[y][x] < mp[ny][nx]) {
					mf = min(mf, mp[ny][nx]);
				}
				if (mp[y][x] == mp[ny][nx] && !vis[ny][nx]) {
					cnt++;
					vis[ny][nx] = 1;
					temp.push_back({ ny, nx });
					q.push({ ny,nx });
				}
				
			}
	}
	int cur = mp[a][b];
	for (auto [y, x] : temp) {
		mp[y][x] += (mf - cur);
	}
	return cnt * (mf - cur);
}
int main() {
	FAST;
	char c;
	cin >> N >> M;
	REP(i, N)REP(j, M) {
		cin >> c;
		mp[i][j] = c - '0';
	}
	int total = 0;
		REP(i, N)REP(j, M) {
			while (1) { //한 지점에 대해 물을 부을 수 있을때까지 붓습니다.
				int flow = bfs(i, j);
				total += flow;
				if (!flow)break;
			}
		}
	cout << total;
}