[백준/BOJ] 백준 18809번 : Gaaaaaaaaaarden

www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

각각의 색깔 배양액을 적절하게 뿌리는 경우를 모두 고려하고, 그때 배양액이 퍼지는 상황을 고려하는데, 배양액이 동시에 도달하는 것을 판단하는 것은 depth를 이용해 판단하였고, 각각 배양액이 퍼지는것을 discovered에 각각의 숫자표시를 해주어서 문제를 해결했다.

 

코드

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

int n, m;
int g, r;
int board[50][50];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int result = 0;

int Check(vector<pair<int, int>> green, vector<pair<int, int>> red)
{
	int ret = 0;
	vector<vector<int>> discovered(n, vector<int>(m, 0));
	int depth[50][50][3];
	queue<pair<pair<int, int>, int>> q;

	for (int i = 0; i < green.size(); i++)
	{
		discovered[green[i].first][green[i].second] = 1; //초록색은 발견에 1로 표시
		depth[green[i].first][green[i].second][1] = 0;
		q.push(make_pair(green[i], 1));
	}

	for (int i = 0; i < red.size(); i++)
	{
		discovered[red[i].first][red[i].second] = 2; //빨간색은 발견에 2로 표시
		depth[red[i].first][red[i].second][2] = 0;
		q.push(make_pair(red[i], 2));
	}

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

		//꽃이 만들어진 위치일때
		if (discovered[here.first][here.second] == 3)
			continue;

		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 && board[there.first][there.second] != 0 && discovered[there.first][there.second] != here_color && discovered[there.first][there.second] != 3)
			{

				depth[there.first][there.second][here_color] = depth[here.first][here.second][here_color] + 1;

				if (here_color == 1)
				{
					//다른색의 배양액이 동시에 도달한 경우
					if (discovered[there.first][there.second] == 2 && depth[there.first][there.second][1] == depth[there.first][there.second][2])
					{
						//꽃이 만들어진다
						discovered[there.first][there.second] = 3; //꽃이 만들어졌다는것 표시
						ret++;
					}

					else if (discovered[there.first][there.second] == 0)
					{
						discovered[there.first][there.second] = here_color;
						q.push(make_pair(there, here_color));
					}

				}

				else if (here_color == 2)
				{
					if (discovered[there.first][there.second] == 1 && depth[there.first][there.second][1] == depth[there.first][there.second][2])
					{
						//꽃이 만들어진다
						discovered[there.first][there.second] = 3;
						ret++;
					}

					else if (discovered[there.first][there.second] == 0)
					{
						discovered[there.first][there.second] = here_color;
						q.push(make_pair(there, here_color));
					}
				}

			}

		}
	}

	return ret;
}

void Solve(int last_select, vector<pair<int, int>> green, vector<pair<int, int>> red)
{
	//배양액을 더 뿌린게 있을때
	if (green.size() > g || red.size() > r)
		return;

	//배양액을 각각 맞게 다 뿌렸을때
	if (green.size() == g && red.size() == r)
	{
		result = max(result, Check(green, red));
		return;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int this_number = i * m + j;

			if (this_number <= last_select)
				continue;

			if (board[i][j] != 2)
				continue;

			green.push_back(make_pair(i, j)); //해당 위치에 초록색 배양액을 뿌린다
			Solve(this_number, green, red);
			green.pop_back();

			red.push_back(make_pair(i, j)); //해당 위치에 빨간색 배양액을 뿌린다
			Solve(this_number, green, red);
			red.pop_back();
		}
	}
}

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

	cin >> n >> m >> g >> r;

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

			board[i][j] = input;
		}

	vector<pair<int, int>> green;
	vector<pair<int, int>> red;

	Solve(-1, green, red);

	cout << result;

	return 0;
}