[BOJ] 18809 : Gaaaaaaaaaarden

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

---

문제해석

 Green, Red 배양액을 땅에 뿌리고, 배양액이 주변으로 퍼져나가며, Green / Red 배양액이 만나게 되면 Flower가 생긴다.

문제핵심

1. 가능한 땅 중에서 Green, Red 배양액을 무조건 다 뿌려야 된다.

--> Backtracking 을 이용해서 가능한 모든 경우를 구해봐야 한다.

2. Green, Red 배양액이 단순히 만나는 게 아니라 동일한 시간에 도달한 땅에서만 Flower 가 생긴다.

--> 단순히 BFS 탐색만을 진행하면 안 된다.

알고리즘

1. 입력받은 map에서 배양액을 뿌릴 수 있는 vitaminMap을 따로 모아둔다.

2. 백트레킹을 통해 vitaminMap에 Green, Red 배양액을 다 뿌린다.

3. BFS 탐색을 통해서 Green, Red 배양액을 뿌려나갈 건데 다음과 같은 stateMap을 이용한다.

pair<int, int> stateMap[i][j] = (i, j) 에서 { 현재 시간, 현재 상태 } 를 저장한다.

--> 초기 배양액을 뿌린 곳들만 stateMap[i][j] = { 0, Green || Red } 로 초기화한다.

--> BFS 탐색을 통해서 현재 지점에서 다음 지점들로 탐색을 진행해나가는데, 

● 다음 지점의 stateMap 의 상태가 EMPTY 면 Green, Red 배양액이 아직 뿌려지지 않은 Map이므로 Green, Red 배양액을 저장해준다.

● 다음 지점의 stateMap 상태가 Green 이고 현재 상태가 Red 이고 같은 시간에 방문했다면 Flower 를 만듭니다.

● 다음 지점의 stateMap 상태가 Red 이고 현재 상태가 Green 이고 같은 시간에 방문했다면 Flower 를 만듭니다.

알고리즘회고

 처음에는 stateMap 을 이용할 생각을 못하고, 현재 queue에 저장된 Green, Red 에서 다음 지점들을 다 탐색해나가며 nextGreen, nextRed 라고 다음 지점들을 다 따로 저장했다. 그 후, 따로 저장한 지점들을 비교하며 Flower가 만들어지는 지점들을 체크하고 아닌 지점들은 다시 queue에 Push 해주는 방식으로 BFS 탐색을 진행했다. 당연히 시간이 위의 알고리즘에 비해 오래 걸렸고 BarkingDog 님의 코드를 참고해서 알고리즘을 개선할 수 있었다.

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

int N, M, G, R, ans;
int map[50][50]; // 0 은 호수 3은 레드 4는 그린
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
vector<pair<int, int>> vitaminMap;
int vitamin[10]; // 0은 아무것도 안뿌림 1은 레드 2는 그린

const int EMPTY = 0;
const int RED = 3;
const int GREEN = 4;
const int FLOWER = 5;

bool check(int r, int c) {
	if (0 <= r && r < N && 0 <= c && c < M) return true;
	return false;
}

void BFS() {
	int result = 0;
	pair<int, int> state[50][50];
	queue<pair<int, int>> q;
	for (int i = 0; i < vitaminMap.size(); i++) {
		if (vitamin[i] == 0) continue;
		state[vitaminMap[i].first][vitaminMap[i].second] = { 0, vitamin[i] };
		q.push(vitaminMap[i]);
	}
	while (!q.empty()) {
		int curX = q.front().first, curY = q.front().second;
		int curT = state[curX][curY].first, curC = state[curX][curY].second;
		q.pop();
		if (curC == FLOWER) continue;
		for (int dir = 0; dir < 4; dir++) {
			int nX = curX + dx[dir], nY = curY + dy[dir];
			if (!check(nX, nY)) continue; // 범위 밖
			if (map[nX][nY] == 0) continue; // 호수
			if (state[nX][nY].second == EMPTY) {
				state[nX][nY] = { curT + 1, curC };
				q.push({ nX, nY });
			}
			else if (state[nX][nY].second == RED) {
				if (curC == GREEN && state[nX][nY].first == curT + 1) {
					result++;
					state[nX][nY].second = FLOWER;
				}
			}
			else if (state[nX][nY].second == GREEN) {
				if (curC == RED && state[nX][nY].first == curT + 1) {
					result++;
					state[nX][nY].second = FLOWER;
				}
			}
		}
	}
	ans = max(ans, result);
	return;
}

void Backtracking(int s, int curG, int curR) {
	if (curG == G && curR == R) {
		BFS();
		return;
	}
	for (int i = s; i < vitaminMap.size(); i++) {
		if (vitamin[i] == 0 && curG < G) {
			vitamin[i] = GREEN;
			Backtracking(i + 1, curG + 1, curR);
			vitamin[i] = 0;
		}
		if (vitamin[i] == 0 && curR < R) {
			vitamin[i] = RED;
			Backtracking(i + 1, curG, curR + 1);
			vitamin[i] = 0;
		}
	}
	return;
}

int main(void) {
	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 >> map[i][j];
			if (map[i][j] == 2) vitaminMap.push_back({ i, j });
		}

	Backtracking(0, 0, 0);

	cout << ans << '\n';
	return 0;
}

---