[BOJ-18809] Gaaaaaaaaaarden (C++)

백준 18809 - Gaaaaaaaaaarden  

 

18809번: Gaaaaaaaaaarden

 

문제 설명

 

 - BOJ마을에 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피우려 한다.

 

 - 배양액은 매 초마다 도달한 적이 없는 인접한 땅으로 퍼져간다.

 

 - 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 경우 꽃이 피어난다.

 

 - 꽃이 피어난 땅에는 배양액이 사라져서 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

 

 - 배양액은 모두 사용해야 하고, 배양액을 사용할 수 있는 땅은 따로 존재한다.

 

 - 또한, 배양액은 모두 서로 다른 곳에 뿌려져야 한다.

 

 - 정원과 두 배양액의 개수가 주어졌을 때 피울 수 있는 꽃의 최대 개수를 구하라.

 

---

 

입력 값

 

 - 첫째 줄에는 정원의 행 개수(N)와 열 개(R)가 주어진다.

   (2 <= N <= 50, 2 <= M <= 50)

 

 - 그리고 초록색 배양액의 개수(G)와 빨간색 배양액의 개수(R)이 주어진다.

   (1 <= G <= 5, 1<= R <= 5)

 

 - 그 다음 N개의 줄에는 M개의 정원에 대한 정보가 주어진다.

 

 - 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅.

   (호수로는 배양액이 퍼지지 않는다.)

 

 - 배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고, 10개 이하이다.

 

---

 

예제

---

 

 

문제 분석

 

 - 초록색 배양액과 빨간색 배양액이 뿌려진 위치가 처음에 주어진것이 아니라, 각 배양액 개수와 배양액이 뿌려질 수 있는

   땅의 위치가 주어졌다.  

   => 배양액이 어떠한 위치에 뿌려져야 하는지 경우의 수를 모두 구해야 한다.

 

 - 배양액이 뿌려질 땅이 정해지면, 해당 배양액이 퍼지는 경우를 구하여 꽃이 피워지는 개수를 구하면 된다.

 

 - BFS를 이용하여 각 초마다 배양액이 어떻게 퍼지는지 살펴보고, 초록색 배양액과 빨간색 배양액이 만나는지 판별하면 된다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

#define GREEN 3
#define RED 4
#define FLOWER 5

// 땅의 정보. 
// color => 땅의 색, time => 해당 땅에 배양액이 뿌려진 시간.
struct myPoint {
	int color;
	int time;

};

int dx[]{ 0,0,-1,1 };
int dy[]{ 1,-1,0,0};

int N;
int M;

// 배양액이 뿌려질 수 있는 땅의 위치
vector<pair<int, int>> colorPoint;

// 땅의 정보가 담겨 있는 벡터
vector<vector<myPoint>> baseV;

int bfs( vector<vector<myPoint>> v)
{
	queue<pair<int,int>> q;

	pair<int, int> nowNode;

	int result = 0;

	for (int i = 0; i<N; i++)
	{

		for (int j = 0; j < M; j++)
		{
			// 배양액이 초기에 뿌려진 위치를 큐에 넣는다.
			if (v[i][j].color == RED || v[i][j].color == GREEN)
				q.push({ i, j });
		}

	}

	while (!q.empty())
	{
		nowNode = q.front();
		q.pop();

		int x = nowNode.first;
		int y = nowNode.second;

		// 해당 위치에 꽃이 피어 있다면, 더 이상 퍼지지 않는다.
		if (v[x][y].color == FLOWER)
			continue;

		for (int di = 0; di < 4; di++)
		{
			int nx = x + dx[di];
			int ny = y + dy[di];

			if (nx >= 0 && nx < N && ny >= 0 && ny < M && v[nx][ny].color!=0 && v[nx][ny].color!=FLOWER)
			{
				// 해당 땅에 배양액에 뿌려지지 않은 경우
				if (v[nx][ny].color==1)
				{
					q.push({ nx,ny });
					v[nx][ny].color = v[x][y].color;
					v[nx][ny].time = v[x][y].time+1;
				}

				// 해당 땅에 배양액이 뿌려져 있고,
				// 해당 배양액이 지금 퍼지고 있는 배양액과 다르고, 뿌려지는 시간이 같은 경우
				else if ((v[nx][ny].color != v[x][y].color) && (v[x][y].time+1 == v[nx][ny].time))
				{
					result++;
					v[nx][ny].color = FLOWER;
				}

			}
		}
	}

	return result;
}

// 배양액이 뿌려질 수 있는 땅에 
// 어떠한 배양액이 뿌려져야 하는지 모든 경우를 계산
int solution(int R,int G, int index, vector<int> col)
{
	int result = 0;

	// 남아 있는 배양액 보다, 뿌려질 수 있는 땅의 개수가 적은 경우
	if (R + G > col.size() - index)
		return -1;
	
	// 모든 땅을 모두 살펴본 경우 BFS를 실행시킨다.
	if (index==col.size())
	{	
		vector<vector<myPoint>> v(baseV);

		for (int i = 0; i < col.size(); i++)
		{
			int x = colorPoint[i].first;
			int y = colorPoint[i].second;

			v[x][y].color = col[i];
		}

		return bfs(v);
	}


	// 땅에 빨간색 배양액을 뿌리는 경우.
	if (R > 0)
	{
		col[index] = RED;

		result = max(result, solution(R-1, G, index + 1, col));

		col[index] = 1;
	}

	// 땅에 초록색 배양액을 뿌리는 경우.
	if(G > 0)
	{
		col[index] = GREEN;

		result = max(result, solution(R, G-1, index + 1, col));

		col[index] = 1;
	}

	result = max(result, solution(R, G, index + 1, col));

	return result;
}




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

	int C;
	int R, G;

	cin >> N;
	cin >> M;
	
	cin >> G;
	cin >> R;

	vector<int> v;

	for (int i = 0; i<N; i++)
	{
		baseV.push_back({});
		for (int j = 0; j < M; j++)
		{
			cin >> C;

			baseV[i].push_back({ C,0 });

			// 배양액이 뿌려질 수 있는 땅을 따로 저장해 놓는다.
			if (C == 2)
			{
				colorPoint.push_back({ i,j });
				v.push_back(1);
			}

		}
	}

	cout << solution(R, G, 0, v) << endl;

	return 0;
}