[BOJ/백준 18809/C++] Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

 

[문제 요약]

-  정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.

-  초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

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

- 아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.

- 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

- 아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.

- 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.

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

- 정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.

[문제 조건]

- 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.

- 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다.

- 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.

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

- 시간 제한 : 2초

- 메모리 제한 : 512MB

 

[문제 풀이]

이 문제는 얼핏 보면 간단해보이지만 생각보다 생각해야 될게 많은 탐색+구현 문제였다.

 

먼저 우리가 생각해야될 것을 알아보자.

• 배양액을 뿌릴 수 있는 땅을 R+G개 만큼 선택
• 선택된 땅에 빨간색 배양액과 초록색 배양액을 조합하여 배치
• 배양액들을 확장시키면서 같은 시간에 같은 칸에 서로 다른 배양액이 도달한 경우 꽃으로 판단하고 개수를 증가

위 3개를 생각해야 될 것이다.

 

먼저 땅을 선택하는 방법은 필자는 다음과 같이 선택했다.

처음에 데이터를 입력받을때 배양액을 뿌릴 수 있는 땅들을 vector에 저장해놓고 DFS를 이용하여 R+G개 만큼 선택하였다.

 

다음으로 배양액을 뿌리는 방법은 서로 다른 vector 2개에 각각 R개, G갬 만큼 3과 4를 집어넣어 주고 next_permutation 함수를 이용하여 모든 경우의 조합을 구한 다음 선택된 배양액을 뿌릴 수 있는 땅에 맵핑 시키는 방식으로 배양액을 뿌렸다.

 

void simulation(int cur, int depth)
{
	if (depth == R + G)
	{
		do
		{
			//
   		} while (next_permutation(water.begin(), water.end()));
	}

	for (int i = cur; i < farm_land.size(); i++)
	{
		selected.push_back(farm_land[i]);
		simulation(i + 1, depth + 1);
		selected.pop_back();
	}
}

 

다음으로 배양액들의 위치를 결정했으면 BFS를 이용하여 확장 시켰다.

 

dummy라는 원소가 pair<int,int>고 2차원 배열을 이용하여 pair의 first는 그 칸에 존재하는 배양액의 종류를 의미하고, second는 그 배양액이 도달한 시간을 의미한다.

 

만약 first의 값이 3이면 빨간색만, 4면 초록색만 존해한다는 것이고 7이면 꽃을 의미한다.

 

따라서 배양액들을 확장하면서 어떤 배양액이 이미 배양액이 존재하면서 같은 시간에 도달한 칸에 개수들을 세어주면서 BFS를 진행해주면 문제가 풀리게 된다.

 

[소스 코드]

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

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

using namespace std;

int N, M, G, R;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
vector<vector<int>> mp;
vector<pii> farm_land;
vector<pii> selected;
vector<int> water;
int ans = 0;

void simulation(int cur, int depth)
{
	if (depth == R + G)
	{
		do
		{
			vector<vector<pii>> dummy;
			dummy.resize(N); for (int i = 0; i < N; i++) dummy[i].resize(M);
			queue<pii> q;
			for (int i = 0; i < selected.size(); i++)
			{
				dummy[selected[i].first][selected[i].second] = { water[i], 0 };
				q.push({ selected[i].first, selected[i].second });
			}
			int flower = 0;
			while (!q.empty())
			{
				pii tmp = q.front(); q.pop();
				int y = tmp.first;
				int x = tmp.second;

				if (dummy[y][x].first == 7) continue;

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

					if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
					if (mp[ny][nx] == 0) continue;

					//새로 가는 곳이 배양액이 없는 칸이면
					if (dummy[ny][nx].first == 0)
					{
						dummy[ny][nx].first = dummy[y][x].first;
						dummy[ny][nx].second = dummy[y][x].second + 1;
						q.push({ ny,nx });
					}
                    //배양이 뭐라도 있으면서
					else if (dummy[ny][nx].first != 7)
					{
                    	//같은 시간에 도달한 곳이면
						if (dummy[ny][nx].first != dummy[y][x].first && dummy[ny][nx].second == dummy[y][x].second + 1)
						{
							dummy[ny][nx].first = 7;
							flower++;
						}
					}
				}
			}
			ans = max(ans, flower);
		} while (next_permutation(water.begin(), water.end()));
	}

	for (int i = cur; i < farm_land.size(); i++)
	{
		selected.push_back(farm_land[i]);
		simulation(i + 1, depth + 1);
		selected.pop_back();
	}
}

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

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> mp[i][j];
			if (mp[i][j] == 2) farm_land.push_back({ i,j });
		}
	}
	
	for (int i = 0; i < G; i++) water.push_back(3);
	for (int i = 0; i < R; i++) water.push_back(4);

	simulation(0, 0);

	cout << ans;
}

DFS + BFS 가 혼합된 환장의 문제

굳