백준(BOJ) 18809번 Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

 

풀이 :

 

loc 배열에는 0과 g에 개수만큼 1이, r에 개수만큼 2가 들어있다. 이 loc 배열을 next_permutation을 통해 어느 좌표에 g

 

와 r을 넣어야 하는지에 대한 모든 경우의 수를 돌려볼 수가 있다. g와 r을 넣을 수 있는 cand 좌표 벡터를 만든 후 g와 r

 

에 위치를 큐에 집어넣었다면 꽃의 개수를 찾는다.

 

꽃의 개수를 찾을 때에는 st pair 2차원 벡터를 통해 { 현재시간, 어떤 색깔 } 찾게 되며

 

색깔이 없다면 방문할 수 있는 곳이며 큐에 넣어주고

 

색깔이 이미 있다면 현재시간과 지금 들어온 색깔을 비교해 꽃이 될 수 있는지 확인한다.

 

이미 꽃이 된 좌표는 큐에서 꺼낼 때 무시한다.  st[y][x].second == 3인 경우 

 

코드 ( C++ )

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	int n, m, g, r;
	int board[55][55];
	vector<pair<int, int>> cand;
	// 0은 기본 1은 그린 2는 레드 3은 꽃
	vector<int> loc;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int solve()
	{
	pair<int, int> st[55][55];
	queue<pair<int, int>> q;
	for (int i = 0; i < cand.size(); ++i) {
	if (loc[i] == 0) continue;
	int y = cand[i].first;
	int x = cand[i].second;
	q.push({ y,x });
	st[y][x] = { 0,loc[i] };
	}
	int cnt = 0;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	int time = st[y][x].first;
	int who = st[y][x].second;
	q.pop();
	if(st[y][x].second == 3) continue;
	for (int k = 0; k < 4; ++k) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < m)) continue;
	if (board[ny][nx] == 0) continue;
	if (st[ny][nx].second == 0) {
	st[ny][nx] = { time + 1, who };
	q.push({ ny,nx });
	}
	else if (st[ny][nx].second == 1) {
	if (who == 2 && time + 1 == st[ny][nx].first) {
	cnt += 1;
	st[ny][nx].second = 3;
	}
	}
	else if (st[ny][nx].second == 2) {
	if (who == 1 && time + 1 == st[ny][nx].first) {
	cnt += 1;
	st[ny][nx].second = 3;
	}
	}
	}
	}
	return cnt;
	}
	int main()
	{
	ios_base::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];
	if (board[i][j] == 2) {
	cand.push_back({ i,j });
	loc.push_back(0);
	}
	}
	for (int i = 0; i < loc.size(); ++i) {
	if (g > 0) {
	loc[i] = 1;
	g -= 1;
	}
	else if (r > 0) {
	loc[i] = 2;
	r -= 1;
	}
	}
	sort(loc.begin(), loc.end());
	int ans = 0;
	do {
	ans = max(ans, solve());
	} while (next_permutation(loc.begin(), loc.end()));
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub