[알고리즘] C++ 백준 18809 Gaaaaaaaaaarden

 

백준 18809

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

18809번: Gaaaaaaaaaarden

 

풀이 전 나의 생각

 DFS와  BFS를 동시에 사용하여 풀 수있는 문제다.

초록색, 빨간색의 배양액을 뿌릴 수 있는 경우의 수를 모두 구해야 한다. 이는 DFS로 모든 경우의 수를 구하여 탐색이 가능하다.

이는 초록 배양액의 위치를 정한 후 빨간 배양액의 위치를 정하면 쉽게 구할 수 있다.  

다음으로 배양액의 위치를 모두 정했으면 배양액이 어느 위치를 몇초에 갈 수있는지 양방향 탐색을 이용한 BFS를 이용하여 구할 수있다

풀이에서는 초록 배양액-> 빨간 배양액 순서로 받았기 때문에 BFS에서도 이 순서대로 진행한다. 원본값에 영향을 주지 않기 위해 배양액의 위치와 현재 땅의 위치를 카피하고 배양액의 위치부터 양방향 탐색을 진행한다.
초록 배양액의 탐색이 끝났다면 1초가 지난 후  땅의 결과가 나올 것이다. 그 다음 빨간 배양액의 탐색을 진행하면 마찬가지로 1초가 지난 후 땅의 결과가 나온다.

그럼 이제 배양액이 맞닿아서 꽃이 필 수있는지 없는지를 마지막으로 검사한다. 꽃이 필수 있다면 꽃이 핀 위치에서는 더 이상 배양액이 퍼지지  않기 때문에 피었다는 확인만 해주고 넘어간다. 반대로 꽃이 필 수 없다면 다시 다음위치를 큐에넣고 탐색을 진행한다.

모든 배양액의 탐색이 끝났다면 최종적으로 꽃이 얼마나 폈는지 확인해준다.
여기서 주의할점은 DFS의 분기를 통해 BFS에서 선언된 공간의 값들은 BFS가 끝날 시 모두 초기화 해주어야 한다.  DFS를 진행하기 전 방문 표시를 해주고 DFS가 끝나면 방문 표시를 다시 원상태로 복구해주는 것 처럼 어느 한 분기가 끝나면 값을 다시 초기값으로 복구해주는 과정이라고 생각하면된다

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>

using namespace std;

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

int n, m, g, r = 0;
int board[51][51];
int copy_Board[51][51];
int check_Green[51][51];
int check_Red[51][51];
int check_land[51][51];

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

typedef struct qu
{
	int x;
	int y;
	int t;
}qu;

int ans;


void BFS()
{
	queue<qu> G_q;
	queue<qu> R_q;
	int flower = 0;

	for (int i = 0; i < g; i++)
	{
		int x = green[i];
		copy_Board[land[x].first][land[x].second] = 3;
		check_Green[land[x].first][land[x].second] = 1;
		G_q.push({ land[x].first, land[x].second, 1 });
	}

	for (int i = 0; i < r; i++)
	{
		int x = red[i];
		copy_Board[land[x].first][land[x].second] = 4;
		check_Red[land[x].first][land[x].second] = 1;
		R_q.push({ land[x].first, land[x].second, 1 });
	}

	while (!G_q.empty() || !R_q.empty())
	{
		int G_size = G_q.size();
		int R_size = R_q.size();

		for (int k = 0; k < G_size; k++)
		{
			int x = G_q.front().x;
			int y = G_q.front().y;
			int t = G_q.front().t;
			G_q.pop();
			if (copy_Board[x][y] == -1) continue;

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

				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

				if (check_Green[nx][ny] == 0 && (copy_Board[nx][ny] == 1 || copy_Board[nx][ny] == 2))
				{
					check_Green[nx][ny] = t + 1;
					G_q.push({ nx, ny, t + 1 });
					copy_Board[nx][ny] = 3;
				}

			}
		}

		for (int k = 0; k < R_size; k++)
		{
			int x = R_q.front().x;
			int y = R_q.front().y;
			int t = R_q.front().t;
			R_q.pop();

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

				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

				if (check_Red[nx][ny] == 0 && (copy_Board[nx][ny] == 1 || copy_Board[nx][ny] == 2))
				{
					check_Red[nx][ny] = t + 1;
					R_q.push({ nx, ny, t + 1 });
					copy_Board[nx][ny] = 4;
				}

				else if (check_Red[nx][ny] == 0 && copy_Board[nx][ny] == 3)
				{
					if (check_Green[nx][ny] == t + 1)
					{
						copy_Board[nx][ny] = -1;
						check_Red[nx][ny] = t + 1;
					}
				}

			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (copy_Board[i][j] == -1) flower++;
		}
	}
	ans = max(ans, flower);
}

void reset_board()
{
	memset(check_Green, 0, sizeof(check_Green));
	memset(check_Red, 0, sizeof(check_Red));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			copy_Board[i][j] = board[i][j];
		}
	}
}

void select_red(int start, int cnt)
{
	if (cnt == r)
	{
		BFS();
		reset_board();
	}
	else
	{
		for (int i = start; i < land.size(); i++)
		{
			if (check_land[land[i].first][land[i].second] == 0)
			{
				check_land[land[i].first][land[i].second] = 1;
				red.push_back(i);
				select_red(i, cnt + 1);
				check_land[land[i].first][land[i].second] = 0;
				red.pop_back();
			}
		}
	}
}

void select_green(int start, int cnt)
{
	if (cnt == g)
	{
		select_red(0, 0);
	}
	else
	{
		for (int i = start; i < land.size(); i++)
		{
			if (check_land[land[i].first][land[i].second] == 0)
			{
				check_land[land[i].first][land[i].second] = 1;
				green.push_back(i);
				select_green(i, cnt + 1);
				check_land[land[i].first][land[i].second] = 0;
				green.pop_back();
			}
		}
	}
}

void solve()
{
	select_green(0, 0);
	cout << ans;
}

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

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
			copy_Board[i][j] = board[i][j];

			if (board[i][j] == 2) land.push_back({ i, j });
		}
	}

	solve();
	return 0;
}