[BOJ/백준 1113/C++] 수영장 만들기

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

1113번: 수영장 만들기

 

[문제 요약]

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

16661
61116
16661

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

 

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

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

 

[문제 조건]

- 첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다.

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

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

이번문제는 탐색(BFS)과 구현이 합쳐진 문제다.

 

일단 수영장을 만들려면 물이 고이는 칸들을 찾아야한다. 이때 외곽에 있는 모든 칸들 (x==0 || y==0 || x==C-1 || y==R-1)의 경우는 모두 맵 밖으로 나가기 때문에 절대로 물을 채울 수가 없다.

 

따라서 필자는 다음과 같은 방식으로 구현하였다.

• 입력으로 주어지는 2차원배열 (mp)의 원소를 하나씩 확인하면서 그 원소와 같은 값을 찾는 상하좌우로 최대로 연결되는 모든 칸들을 탐색한다. 
• 탐색하면서 원소보다 작은 값이 주변에 존재한다면 around_small의 값을 true로 바꿔준다. around_small이 의미하는 것은 주변에 이 그룹보다 낮은 땅이 존재한다는 것을 표시한 것이다.
• 탐색하면서 (행의 값이 0이거나 R-1) 이거나 (열의 값이 0이거나 C-1) 일 경우 외곽에 있다는 것을 의미하는 suburd를 true로 바꿔준다.
• 탐색하면서 이 그룹보다 큰 값을 가지면서 가장 작은 값을 찾으면 min_v에 저장한다. min_v는 나중에 이 그룹의 값들을 min_v로 교체할때 사용한다. 정답을 의미하는 ans에  (min_v - 원소의 값)만큼 더 해주면 그 그룹에 각각 (min_v - 원소의 값) 만큼 물을 부을 수 있다는 것이다.
• around_small == false , suburd == false , min_v가 한번이라도 갱신되었다면 그 그룹에 대해 물을 붓는다. 이때 바로 물을 붓는 것이 아니라 update배열에 { {좌표} , 바꿀 값 } 을 저장해서 mp배열에 대한 탐색이 모두 끝난 후 한꺼번에 바꿔주어야 한다.
• 이때 한번이라도 mp에 대한 갱신이 일어나지 않으면 더 이상 물을 부을 공간이 없기 때문에 반복을 종료한다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int R, C;
int dx[4] = { 1, 0 ,-1 ,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<int>> mp;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> R >> C;
	mp.resize(R);
	for (int i = 0; i < R; i++) mp[i].resize(C);

	for (int i = 0; i < R; i++)
	{ 
		for (int j = 0; j < C; j++)
		{
			char tmp;
			cin >> tmp;
			mp[i][j] = tmp - '0';
		}
	}

	int ans = 0;
	while (1)
	{
		bool fin = true;
		vector<vector<bool>> ck(R, vector<bool>(C, 0));
		vector<pair<pii,int>> update;
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				if (ck[i][j]) continue;
				queue<pii> q;
				vector<pii> pos;
				pos.push_back({ i,j }); q.push({ i,j });
				ck[i][j] = true;
				bool around_small = false;
				bool suburd = false;
				int min_v = INF;
				while (!q.empty())
				{
					pii tmp = q.front(); q.pop();
					if (tmp.first == 0 || tmp.first == R - 1 || tmp.second == 0 || tmp.second == C - 1) suburd = true;
					for (int k = 0; k < 4; k++)
					{
						int nx = tmp.second + dx[k];
						int ny = tmp.first + dy[k];

						if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;

						if (mp[ny][nx] > mp[i][j]) min_v = min(min_v, mp[ny][nx]);		
						else if (mp[ny][nx] < mp[i][j]) around_small = true;
						else
						{
							if (!ck[ny][nx])
							{
								ck[ny][nx] = true; q.push({ ny, nx }); pos.push_back({ ny,nx });
							}
						}
					}
				}
				if (!around_small && !suburd && min_v != INF)
				{
					fin = false;
					for (int k = 0; k < pos.size(); k++)
					{
						update.push_back({ {pos[k].first,pos[k].second}, min_v });
						ans += (min_v - mp[i][j]);
					}
				}
			}
		}
		if (fin) break;

		for (int i = 0; i < update.size(); i++)
			mp[update[i].first.first][update[i].first.second] = update[i].second;
		
	}
	cout << ans;
}

굳