문제 : 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;
}
