백준 18809번 Gaaaaaaaaaarden C++

출처 : https://www.acmicpc.net/problem/18809

 

1. 배양액을 뿌릴 수 있는 땅의 그룹을 만든다.

   (예제 2의 입력을 예로 들면 (0, 0), (2, 0), (2, 2))

 

2. 배양액을 뿌릴 수 있는 땅의 그룹 중 r + g 만큼의 땅의 그룹들을 백트래킹을 이용하여 모두 찾는다.

   (예제 2의 입력을 예로 들면 g는 2, r는 1이어서 r + g는 3 이기 때문에 1번과 같다.)

   (만약 g = 1, r = 1 이었다면 r + g = 2 이기 때문에 (0, 0), (2, 0) 과 (0, 0), (2, 2) 과 (2, 0), (2, 2) 세 가지 경우가 나옴)

 

3. 2에서 찾은 그룹을 r 그룹과 g 그룹으로 나눈다.

   (예제 2의 입력을 예로 들면 g는 2, r는 1이기 때문에

     g : (0, 0), (2, 0) , r : (2, 2)

     g : (0, 0), (2, 2) , r : (2, 0)

     g : (2, 0), (2, 2) , r : (0, 0) 이렇게 세가지 경우가 나온다.

 

4. 각각의 경우마다 시간 정보와 함께 큐에 넣고 bfs 탐색을 통해 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, m, g, r;
vector<vector<pair<int, int>>> board(50, vector<pair<int, int>>(50));
vector<pair<int, int>> possible_locate; //배양액을 뿌릴 수 있는 땅
vector<pair<int, int>> start_locate; // 배양액을 뿌릴 수 있는 땅 중 r + g 만큼의 땅을 저장
vector<pair<int, int>> red_start; //start_locate 중 r만큼의 땅
vector<pair<int, int>> green_start; // start_locate 중 g 만큼의 땅
vector<int> red_indexes;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
int ans = 0;

enum Color {
	red=3,
	green=4
};

struct med { //배양액의 정보를 담기 위한 구초제
	med(int color, int time, pair<int, int> locate) :color(color), time(time), locate(locate) {};
	int color;
	int time;
	pair<int, int> locate;
};

void bfs() {
	int flower = 0;
	queue<med> q;
	vector<vector<pair<int, int>>> tmp_board(50, vector<pair<int, int>>(50));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			tmp_board[i][j] = board[i][j];
		}
	}
	for (int i = 0; i < r; i++) {
		q.push(med(Color::red, 0, red_start[i]));
		tmp_board[red_start[i].first][red_start[i].second] = { Color::red,0 };
	}
	for (int i = 0; i < g; i++) {
		q.push(med(Color::green, 0, green_start[i]));
		tmp_board[green_start[i].first][green_start[i].second] = { Color::green,0 };
	}
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (tmp_board[curr.locate.first][curr.locate.second].first == 5) continue;
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.locate.first + dRow[i];
			int nextCol = curr.locate.second + dCol[i];
			if (nextRow < 0 || nextRow >= n) continue;
			if (nextCol < 0 || nextCol >= m) continue;
			if (tmp_board[nextRow][nextCol].first == 0) continue;
			if (tmp_board[nextRow][nextCol].first == 5) continue;
			if (tmp_board[nextRow][nextCol].first == Color::green) {
				if (curr.color == Color::green) continue;
				if (curr.time + 1 != tmp_board[nextRow][nextCol].second) continue;
				tmp_board[nextRow][nextCol].first = 5;
				flower++;
				continue;
			}
			if (tmp_board[nextRow][nextCol].first == Color::red) {
				if (curr.color == Color::red) continue;
				if (curr.time + 1 != tmp_board[nextRow][nextCol].second) continue;
				tmp_board[nextRow][nextCol].first = 5;
				flower++;
				continue;
			}
			q.push(med(curr.color, curr.time + 1, { nextRow, nextCol }));
			tmp_board[nextRow][nextCol].first = curr.color;
			tmp_board[nextRow][nextCol].second = curr.time + 1;
		}
	}
	ans = max(ans, flower);
}

void BT_2(int idx, int cnt) {
	if (cnt >= r) {
		int index = 0;
		for (int i = 0; i < start_locate.size(); i++) {
			if (index < red_indexes.size() && red_indexes[index] == i) {
				red_start.push_back(start_locate[i]);
				index++;
			}
			else {
				green_start.push_back(start_locate[i]);
			}
		}
		bfs();
		red_start.clear();
		green_start.clear();
		return;
	}
	for (int i = idx; i < start_locate.size(); i++) {
		red_indexes.push_back(i);
		BT_2(i + 1, cnt + 1);
		red_indexes.pop_back();
	}
}

void BT(int idx, int cnt) {
	if (cnt >= r + g) {
		BT_2(0, 0);
		return;
	}
	for (int i = idx; i < possible_locate.size(); i++) {
		start_locate.push_back(possible_locate[i]);
		BT(i + 1, cnt + 1);
		start_locate.pop_back();
	}
}

int main() {
	ios_base::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++) {
			int input;
			cin >> input;
			board[i][j] = { input,0 };
			if (input == 2) {
				possible_locate.push_back({ i,j });
			}
		}
	}
	BT(0, 0);
	cout << ans;
};