[백준/BOJ] 백준 1113번 : 수영장 만들기

www.acmicpc.net/problem/1113

1113번: 수영장 만들기

각각의 위치에서 물을 넣었을 때 그때의 결과를 확인한다, Solve(pair<int, int> start) 함수를 통해 start위치에 물을 넣을 때 상황을 확인했는데, 이때 물이 바깥으로 넘치면 안 되며, 물을 넣는 곳의 높이 이하의 위치로만 물이 흐를 수 있다. 그리고 그렇게 흐른 위치들을 checked에 저장하고, checked의 테두리의 가장 낮은 높이를 구해서 각 칸에 채워지는 물을 구한다. 주의해야 될 점은 start가 아닌 다른칸에서 물을 넣어서 해당 칸에 채워지는 물의 양이 더 많을 수 있으므로 해당 위치에 이미 저장된 채워진 물의 양과 지금 채워지는 물의 양 중 더 큰 값을 넣는다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <string>
using namespace std;

int n, m;
vector<vector<int>> board(50, vector<int>(50, 0));
vector<vector<int>> result(50, vector<int>(50, 0));
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//start위치에 물을 넣는다고 했을때 상황을 확인한다
void Solve(pair<int, int> start)
{
	vector<vector<int>> discovered(50, vector<int>(50, 0));
	queue<pair<int, int>> q;
	int start_height = board[start.first][start.second];
	vector<pair<int, int>> checked;

	discovered[start.first][start.second] = 1;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		checked.push_back(here);

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			//물이 바깥으로 넘칠때
			if (there.first < 0 || there.first >= n || there.second < 0 || there.second >= m)
			{
				checked.clear();

				return;
			}

			//물을 넣는곳의 높이 이하의 높이로만 물이 흐를 수 있다
			if (discovered[there.first][there.second] == 0 && board[there.first][there.second] <= start_height)
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}


	vector<vector<int>> checked_board(50, vector<int>(50, 0));
	for (int i = 0; i < checked.size(); i++)
	{
		checked_board[checked[i].first][checked[i].second] = 1;
	}


	//checked의 테두리의 가장 낮은 높이를 구한다
	int min_wall = 987654321;
	for (int i = 0; i < checked.size(); i++)
	{
		pair<int, int> here = checked[i];

		for (int j = 0; j < 4; j++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[j][0], here.second + dxdy[j][1]);

			if (checked_board[there.first][there.second] == 1)
				continue;

			min_wall = min(min_wall, board[there.first][there.second]);
		}
	}

	//result의 각 칸에 채워지는 물을 저장한다
	//주의해야 될 점은 start가 아닌 다른칸에서 물을 넣어서 해당칸에 채워지는 물의 양이 더 많을 수 있으므로
	//해당 위치의 result에 저장된 채워진 물의 양과 지금 채워지는 물의 양을 max를 해서 더 큰값을 넣는다
	for (int i = 0; i < checked.size(); i++)
	{
		result[checked[i].first][checked[i].second] = max(result[checked[i].first][checked[i].second], min_wall - board[checked[i].first][checked[i].second]);
	}


}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < m; j++)
		{
			board[i][j] = (input[j] - '0');
		}
	}

	//모든 위치에서 물을 넣을때 상황을 고려한다
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			Solve(make_pair(i, j));

	int water = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			water += result[i][j];

	cout << water;

	return 0;
}