[백준 18809] Gaaaaaaaaaarden

분류 : dfs+bfs

 

요구사항

배양액을 알맞게 뿌려 피울 수 있는 꽃의 최대 개수 구하기

 

풀이

1. DFS로 배양액을 뿌릴 장소 구하기

2. DFS로 장소에 어떤 배양액 뿌릴지 구하기

3. BFS로 꽃이 피는가 선택

3번은 (1)레드배양액 먼저 이동하고 (2)블루배양액 이동하는데 두개 이동이 끝나고 두개가 도착한 곳이라면 꽃으로 표시한다. 꽃으로 표시하고 꽃이 핀 부분에는 이동 못하니깐 따로 표시해준다

 

코드가 많이 지저분하다..

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct go {
	int x;
	int y;
};
int n, m, r, g;

int map[55][55];
int visit[55][55];
int Pvisit[15];
vector<go> possible;
int counta = 0;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int flower = 0;
vector<int> sel;
int Svisit[15] = { 0, };
void bfs(int arr[][55],queue<go> red, queue<go> blue) {
	int flowercnt = 0;
	while (true) {
		int redsize = red.size();
		int bluesize = blue.size();
		if (redsize == 0 && bluesize == 0)
			break;

		//red 먼저
		//cout << "cnt" << endl;
		for (int i = 0; i < redsize; i++) {
			int r = red.front().x;
			int c = red.front().y;
		//	cout << "Redr " << r << " " << c << endl;
			red.pop();
			if (visit[r][c] == 5) continue;
			for (int j = 0; j < 4; j++) {
				int nr = r + dr[j];
				int nc = c + dc[j];
				if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
				if (arr[nr][nc] == 0) continue;
				if (visit[nr][nc] == 5) continue;

				if (arr[nr][nc] == 1 || arr[nr][nc] == 2) {
					if (visit[nr][nc] == 0) {
						visit[nr][nc] = 2;
						red.push({ nr,nc });
					}
				}
			}
			visit[r][c] = 3;
		}

		for (int i = 0; i < bluesize; i++) {
			int r = blue.front().x;
			int c = blue.front().y;
			blue.pop();
			int flag = 0;
			if (visit[r][c] == 5) continue;
			for (int j = 0; j < 4; j++) {
				int nr = r + dr[j];
				int nc = c + dc[j];
				if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
				if (arr[nr][nc] == 0) continue;
				if (visit[nr][nc] == 5) continue;

				if (arr[nr][nc] == 1 || arr[nr][nc] == 2) {
					if (visit[nr][nc] == 0) {
						visit[nr][nc] = 1;
						blue.push({ nr,nc });
					}
					else if (visit[nr][nc] == 2) {
						visit[nr][nc] = 5;
						flowercnt++;
						flag = 1;
					}
				}
			}
		}

	}
	flower = max(flower, flowercnt);
}
void seldfs(int redcnt, int bluecnt, int now) {
	if (redcnt > r) return;
	if (bluecnt > g) return;
	if (redcnt == r && bluecnt == g) {
		counta++;
		queue<go> redq;
		queue<go> blueq;
		int mapc[55][55];
		memset(visit, 0, sizeof(visit));
		memcpy(mapc, map, sizeof(map));
		for (int i = 0; i < sel.size(); i++) {
			if (Svisit[i] == 1) {
				int r = possible[sel[i]].x;
				int c = possible[sel[i]].y;
				visit[r][c] = 2;
				redq.push({ r,c });
			}
			if (Svisit[i] == 2) {
				int r = possible[sel[i]].x;
				int c = possible[sel[i]].y;
				visit[r][c] = 1;
				blueq.push({ r,c });
			}
		}
		bfs(map, redq, blueq);
		memcpy(map, mapc, sizeof(map));
		return;
	}
	for (int i = now; i < sel.size(); i++) {
		if (Svisit[i] == 0) {
			Svisit[i] = 1;
			seldfs(redcnt + 1, bluecnt, i + 1);
			Svisit[i] = 2;
			seldfs(redcnt, bluecnt + 1, i + 1);
			Svisit[i] = 0;
		}
	}
}
void dfs(int now,int cnt) {
	if(cnt==r+g){
		counta++;
		int mapc[55][55];
		memset(visit, 0, sizeof(visit));
		memcpy(mapc, map, sizeof(map));
		seldfs(0, 0, 0);
		return;
	}
	for (int i = now; i < possible.size(); i++) {
		if (Pvisit[i] == 0) {
			Pvisit[i] = 1;
			sel.push_back(i);
			dfs(i+1,cnt+1);
			sel.pop_back();
			Pvisit[i]=0;
		}
	}
}
int main() {
	scanf("%d%d%d%d", &n, &m, &g, &r);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				possible.push_back({ i,j });
			}
		}
	}
	dfs(0,0);
	cout << flower << endl;

}