[BOJ] 18809 Gaaaaaaaaaarden

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

 

문제 풀이:

 

1. 배양액을 뿌릴 수 있는 땅의 수는 10개 이하이다.
   • 뿌릴 수 있는 곳을 벡터에 따로 저장한다.
2. 두 종류의 배양액을 백트래킹을 이용해서 뿌려준다.
   • 해당 위치에서 가능한 경우의 수는 { (빨간색 배양액 뿌리기), (초록색 배양액 뿌리기), (아무것도 안 뿌리기) } 다음과 같이 3가지 경우가 있다.
   • 빨간색 배양액을 뿌렸다면 rbit에 해당 idx를 사용했다고 체크해준다 (비트마스크)
     • 초록색을 뿌렸다면 gbit에
3. 두 종류의 배양액을 모두 뿌렸다면, bfs를 통해 꽃이 피는 곳을 체크하자.
   • rbit, gbit를 이용해서 초기화를 해준다.
     • 빨강 배양액을 뿌린다면 visit배열에 1로 표시 (+1,+2,+3,...  순으로 퍼져나감)
     • 초록 배양액을 뿌린다면 visit배열에 -1로 표시 (-1, -2, -3, .... 순으로 퍼져나감)
     • bfs를 위해 queue에도 넣어준다.
4. 꽃 핀 곳 처리
   • 지금 visit=본인의 값+1(또는 -1)을 해서 0이 된다면, 두 배양액이 동시에 만나는 것이라고 판단할 수 있다. 이때 cnt++해준다.
   • 꽃 핀 곳에서는 더 이상 퍼져나가면 안 되기 때문에 해당 visit 배열에 적당히 큰 수 10000을 넣어 표시해준다.
   • 현재 visit 배열이 10000이라면 더 이상 퍼져나가지도, cnt를 증가시키지도 않는다. 

 

소스 코드:

#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> P;
vector<P> possible;
queue<pair<P, int>> q;
int n, m, g, r,res,origin[51][51],visit[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void simulation(int rbit,int gbit) {
	int red = 1,green=-1;
	int cnt = 0;

	// 배양액 뿌리기 
	for (int i = 0; i < possible.size(); i++) {
		int curx = possible[i].first;
		int cury = possible[i].second;
		if (rbit&(1 << i)) { // red
			visit[curx][cury] = 1;
			q.push({ {curx,cury},1 });
		}
		else if (gbit&(1 << i)) { //green
			visit[curx][cury] = -1;
			q.push({ {curx,cury},-1 });
		}
	}

	while (!q.empty()) {
		int curx = q.front().first.first;
		int cury = q.front().first.second;
		int flower = q.front().second;
		q.pop();
	
		// 이미 꽃 핀 곳이면 패스
		if (visit[curx][cury] == 10000) continue;
 		
		for (int i = 0; i < 4; i++) {
			int x = curx + dx[i];
			int y = cury + dy[i];
			if (x < 0 || x >= n || y < 0 || y >= m||origin[x][y]==0) continue;
		
			if (visit[x][y] != 0) {
				if (visit[x][y] == 10000) continue;
				if (flower < 0 && visit[x][y] + flower == 1) {
					cnt++;
					visit[x][y] = 10000;
				}
				else if (flower > 0 && visit[x][y] + flower == -1) {
					cnt++;
					visit[x][y] = 10000;
				}
			}
			else {
				if (flower > 0) {
					visit[x][y]=flower+1;
					q.push({ {x,y},flower+1 });
				}
				else {
					visit[x][y]=flower-1;
					q.push({ {x,y},flower -1 });
				}
			}
		}
	}
	res = max(res, cnt);
	memset(visit, 0, sizeof(visit));
}

void putflower(int idx,int red, int green,int rbit,int gbit) {
	if (red == 0 && green == 0) return simulation(rbit,gbit);
	if (red + green > possible.size() - idx) return;

	if (red > 0) {
		putflower(idx + 1, red - 1, green, rbit | (1 << idx), gbit);
	}
	if (green > 0) putflower(idx + 1, red, green - 1, rbit, gbit | (1 << idx));
	
	putflower(idx + 1, red, green, rbit, gbit);
}

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

	cin >> n >> m >> g >> r;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> origin[i][j];
			if (origin[i][j] == 2) {
				possible.push_back({ i,j });
			}
		}
	}
	putflower(0,g,r,0,0);

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