백준 18809 Gaaaaaaaaaarden

Posted by : at

Category : Solution


Problem 문제풀이

 

나의 부족함을 다시 한 번 깨닫게 해주는 문제였다. 간단히 설명하자면 다음과 같다.

 


전략

  1. 배양액을 뿌릴 땅을 정한다.

  2. 배양액이 인접한 땅으로 퍼진다.

  3. 서로 다른 배양액이 동시에 만날 경우 꽃이 핀다.

  4. 2,3을 반복한다.


 

문제를 풀기 위해 두 가지 기능이 필요하다.

  1. 배양액을 뿌릴 땅을 정하는 작업

  2. 배양액을 퍼뜨리는 작업

 

배양액을 뿌릴 땅을 정하는 함수를 이전에 풀었던 N과 M을 참고하여 만들어보자.

먼저 배양액을 뿌릴 수 있는 땅 pair<int,int> soil에서 G+R개의 땅을 선택해야한다.

그 후 선택된 땅에 초록 배양액을 뿌릴지 빨간 배양액을 뿌릴지 결정해야한다.

void solve(int index)
{
	if (index == G + R)
	{
		solve2(0);
	}
	if (index < G + R)
	{
		for (int i = 0; i < soil.size(); i++)
		{
			if (used[i] == 0)
			{
				if (!pos.empty() && pos.back() > i)
				{
					continue;
				}
				pos.push_back(i);
				used[i] = 1;
				solve(index + 1);
				pos.pop_back();
				used[i] = 0;
			}
		}
	}
}

solve()를 통해 G+R개의 땅을 골랐다.

이제 solve2()를 통해 적절하게 분배해보자.

void solve2(int index)
{
	if (index == G)
	{
		for (int i = 0; i < pos.size(); i++)
		{
			if (used2[i] == 0)
			{
				r_pos.push_back(pos[i]);
			}
		}
		tmp = simulation();
		r_pos.clear();
		if (ans < tmp)
		{
			ans = tmp;
		}
		return;
	}
	if (index < G)
	{
		for (int i = 0; i < pos.size(); i++)
		{
			if (used2[i] == 0)
			{
				if (!g_pos.empty() && g_pos.back() > pos[i])
				{
					continue;
				}
				g_pos.push_back(pos[i]);
				used2[i] = 1;
				solve2(index + 1);
				g_pos.pop_back();
				used2[i] = 0;
			}
		}
	}
}

이번 문제에서 가장 실수가 많았던 부분이 solve2()의 구현이었다. ctrl+c + ctrl+v는 정말 좋은 도구이자

정말 위험한 도구이다… 이제 simulation을 구현하자. BFS를 사용할 것이고 queue에는 Growth라는 다음과 같은 struct를 사용할 것이다.

struct Growth {
	int row;
	int col;
	int time;
	int color;
	Growth(int _row, int _col, int _time, int _color) :row(_row), col(_col), time(_time), color(_color) {}
};

queue에 녹색 배양액의 정보와 빨간 배양액의 정보를 담는다. 그리고 퍼뜨린다. 여기서 주의해야할 점이 몇 가지 있다.

 

1.초록 배양액이 먼저 퍼지고 빨간 배양액이 그 다음에 퍼진다.

따라서 빨간 배양액이 퍼질 땅에 초록 배양액이 퍼져있다면

배양액이 퍼진 시간을 확인하고 꽃을 피울지 말지 결정한다.

 

2.초록 배양액이 퍼질 때 꽃이 필지 안 필지는 알 수가 없다.

꽃이 피더라도 queue에 정보가 들어가는 것은 막을 수 없다.

따라서 queue에서 정보를 받아올 때 그 땅에 꽃이 폈는지 아닌지 확인을 해야한다.

int simulation()
{
	int ret = 0;
	pair<int, int> _garden[51][51];
	queue<Growth>q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			_garden[i][j] = { garden[i][j].first,garden[i][j].second };
		}
	}
	for (int i = 0; i < G; i++)
	{
		garden[soil[g_pos[i]].first][soil[g_pos[i]].second] = { 3,0 };
		q.push(Growth(soil[g_pos[i]].first, soil[g_pos[i]].second, 0, 3));
	}
	for (int i = 0; i < R; i++)
	{
		garden[soil[r_pos[i]].first][soil[r_pos[i]].second] = { 4,0 };
		q.push(Growth(soil[r_pos[i]].first, soil[r_pos[i]].second, 0, 4));
	}

	//0 : 호수, 1 : 배양액을 뿌릴 수 없는 땅, 2 : 배양액을 뿌릴 수 있는 땅
	//3 : 초록색 배양액을 뿌린 땅, 4 : 빨간색 배양액을 뿌린 땅 5 : 꽃이 핀 땅
	
	while (!q.empty())
	{
		Growth growth = q.front();
		q.pop();
		if (garden[growth.row][growth.col].first == 5)
		{
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int nR = growth.row + dirR[i];
			int nC = growth.col + dirC[i];
			if (nR >= 0 && nR < N && nC >= 0 && nC < M)
			{
				if (garden[nR][nC].first > 0 && garden[nR][nC].first < 3)
				{
					garden[nR][nC].first = growth.color;
					garden[nR][nC].second = growth.time + 1;
					q.push(Growth(nR, nC, growth.time + 1, growth.color));
				}
				if (growth.color == 4)
				{
					if (garden[nR][nC].first == 3 && garden[nR][nC].second == (growth.time + 1))
					{
						garden[nR][nC].first = 5;
						ret++;
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			garden[i][j] = { _garden[i][j].first, _garden[i][j].second };
		}
	}
	cout << ret << endl;
	return ret;
}

실수가 많은 사람에게 꼭 추천해주고 싶은 문제이다. 이 문제를 오류없이 한 번에 풀 수 있을 정도가 된다면 구현 문제에 자신을 가져도 좋을 것이다.

끝으로 전체 소스코드를 남긴다.

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


struct Growth {
	int row;
	int col;
	int time;
	int color;
	Growth(int _row, int _col, int _time, int _color) :row(_row), col(_col), time(_time), color(_color) {}
};

int N, M, G, R, ans, tmp;
pair<int,int> garden[51][51];
int used[2501];
int used2[2501];
int dirR[4] = { 0,1,0,-1 };
int dirC[4] = { 1,0,-1,0 };
vector<int>g_pos;
vector<int>r_pos;
vector<int>pos;
vector<pair<int, int>>soil;

void solve(int index);
void solve2(int index);
int simulation();

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> G >> R;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> tmp;
			garden[i][j] = { tmp,0 };
			if (tmp == 2)
			{
				soil.push_back({ i,j });
			}
		}
	}
	solve(0);
	cout << ans;
	return 0;
}

void solve(int index)
{
	if (index==G+R)
	{
		solve2(0);
	}
	if (index < G+R)
	{
		for (int i = 0; i < soil.size(); i++)
		{
			if (used[i] == 0)
			{
				if (!pos.empty() && pos.back() > i)
				{
					continue;
				}
				pos.push_back(i);
				used[i] = 1;
				solve(index + 1);
				pos.pop_back();
				used[i] = 0;
			}
		}
	}
}
void solve2(int index)
{
	if (index == G)
	{
		for (int i = 0; i < pos.size(); i++)
		{
			if (used2[i] == 0)
			{
				r_pos.push_back(pos[i]);
			}
		}
		tmp = simulation();
		r_pos.clear();
		if (ans < tmp)
		{
			ans = tmp;
		}
		return;
	}
	if (index < G)
	{
		for (int i = 0; i < pos.size(); i++)
		{
			if (used2[i] == 0)
			{
				if (!g_pos.empty() && g_pos.back() > pos[i])
				{
					continue;
				}
				g_pos.push_back(pos[i]);
				used2[i] = 1;
				solve2(index + 1);
				g_pos.pop_back();
				used2[i] = 0;
			}
		}
	}
}
int simulation()
{
	int ret = 0;
	pair<int,int> _garden[51][51];
	queue<Growth>q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			_garden[i][j] = { garden[i][j].first,garden[i][j].second };
		}
	}
	for (int i = 0; i < G; i++)
	{
		garden[soil[g_pos[i]].first][soil[g_pos[i]].second] = { 3,0 };
		q.push(Growth(soil[g_pos[i]].first, soil[g_pos[i]].second, 0, 3));
	}
	for (int i = 0; i < R; i++)
	{
		garden[soil[r_pos[i]].first][soil[r_pos[i]].second] = { 4,0 };
		q.push(Growth(soil[r_pos[i]].first, soil[r_pos[i]].second, 0, 4));
	}

	//0 : 호수, 1 : 배양액을 뿌릴 수 없는 땅, 2 : 배양액을 뿌릴 수 있는 땅
	//3 : 초록색 배양액을 뿌린 땅, 4 : 빨간색 배양액을 뿌린 땅 5 : 꽃이 핀 땅
	
	while (!q.empty())
	{
		Growth growth = q.front();
		q.pop();
		if (garden[growth.row][growth.col].first == 5)
		{
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int nR = growth.row + dirR[i];
			int nC = growth.col + dirC[i];
			if(nR>=0 && nR<N && nC>=0 &&nC<M)
			{	
				if (garden[nR][nC].first > 0 && garden[nR][nC].first < 3)
				{
					garden[nR][nC].first = growth.color;
					garden[nR][nC].second = growth.time + 1;
					q.push(Growth(nR, nC, growth.time + 1, growth.color));
				}
				if (growth.color == 4)
				{
					if (garden[nR][nC].first == 3 && garden[nR][nC].second == growth.time + 1)
					{
						garden[nR][nC].first = 5;
						ret++;
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			garden[i][j] = { _garden[i][j].first, _garden[i][j].second };
		}
	}
	return ret;
}

End


About GJ

안녕하세요 방문해주셔서 감사합니다. 혹시 보시면서 궁금하신것 있으시면 https://open.kakao.com/o/sivaz71c로 연락주세용~

Star
Useful Links