백준 18809 - Gaaaaaaaaaarden(C++)

문제 링크입니다! https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

DFS를 이용한 선택 + BFS를 이용한 탐색이 합쳐진 문제였습니다(연구소 문제의 심화문제 느낌이였습니다.)

DFS에서 주의할 점이 Green, Red를 선택해야 하는데 겹치면 안된다는 것이였습니다.

따라서 저는 Green -> Red 로 선택해줬습니다.

 

예를들어 1, 2, 3, 4칸에 배양액을 놓을 수 있고, 초록색, 빨간색 배양액을 2개씩 놓는다고 가정하겠습니다.

1. 초록색 (1,2) 선택 -> 빨간색 (3,4) 선택

2. 초록색 (1,3) 선택 -> 빨간색 (2,4) 선택

3. 초록색 (1,4) 선택 -> 빨간색 (2,3) 선택

4. 초록색 (2,3) 선택 -> 빨간색 (1,4) 선택

 .......

이렇게 선택할 수 있게 만들어야합니다.

 

문제 접근 방법

1. 배양액을 놓을 수 있는 위치를 저장한다.

2. DFS를 통해 초록색 배양액을 놓을 수 있는 위치를 찾는다.

3. 초록색 배양액을 G개 만큼 선택하면, 빨간색 배양액을 R개 만큼 선택한다.

4. 배양액들을 모두 선택하면, 초록색 배양액 확산 -> 빨간색 배양액 확산의 순서로 BFS를 실행한다.

5. 전부 탐색했다면, 꽃의 갯수를 확인한 뒤, 가장 큰 수를 출력한다.

 

 

문제 접근 방법 - 2번 + 3번

void select_red(int start, int cnt) {
	if (cnt == R) {
		bfs();
		reset_map();
	}
	else {
		for (int i = start; i < land.size(); i++) {
			if (check_land[land[i].first][land[i].second] == 1) continue;
			check_land[land[i].first][land[i].second] = 1;
			red.push_back(i);
			select_red(i, cnt + 1);
			red.pop_back();
			check_land[land[i].first][land[i].second] = 0;
		}
	}
}

void select_green(int start, int cnt) {
	if (cnt == G) {
		select_red(0, 0);
	}
	else {
		for (int i = start; i < land.size(); i++) {
			if (check_land[land[i].first][land[i].second] == 1) continue;
			check_land[land[i].first][land[i].second] = 1;
			green.push_back(i);
			select_green(i, cnt + 1);
			green.pop_back();
			check_land[land[i].first][land[i].second] = 0;
		}
	}
}

먼저 초록색 배양액을 G개 만큼 선택합니다. 그 다음 빨간색 배양액을 선택합니다.

이때 배양액의 위치가 겹치면 안되기에 이전에 놓지 않았던 곳에 배양액을 놓습니다.

빨간색, 초록색 배양액이 전부 선택되면 BFS 탐색을 실행합니다.

 

 

문제 접근 방법 - 4번(bfs() 함수를 참고해주세요)

저는 초록색 -> 빨간색 순으로 배양액을 퍼트리겠습니다.

초록색이 퍼질 수 있는 경우는

1. 이전에 방문X

2. 호수나 빨간색 배양액의 위치X

해당 위치를 제외하고 초록색 배양액을 퍼트립니다.

 

빨간색이 퍼질 수 있는 경우는

1. 이전에 방문X

2. 호수의 위치X

3. 초록색의 배양액이 있지만, 동시에 퍼지지 않은 경우

만약에 초록색 배양액이 있으면서 동시에 퍼진 위치인 경우에는 꽃을 만들 수 있으므로 꽃을 만들어 줍니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M, G, R;
int map[51][51];
int copy_map[51][51]; //3 -> G , 4 -> R
int check_green[51][51];
int check_red[51][51];
int check_land[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
vector<pair<int, int>> land;
vector<int> green, red;
typedef struct qu {
	int x;
	int y;
	int t;
}qu;
int answer;

void bfs() {
	queue<qu> G_q;
	queue<qu> R_q;
	int flower = 0;
	for (int i = 0; i < G; i++) {
		int x = green[i];
		copy_map[land[x].first][land[x].second] = 3;
		check_green[land[x].first][land[x].second] = 1;
		G_q.push({ land[x].first, land[x].second ,1 });
	}
	for (int i = 0; i < R; i++) {
		int x = red[i];
		copy_map[land[x].first][land[x].second] = 4;
		check_red[land[x].first][land[x].second] = 1;
		R_q.push({ land[x].first, land[x].second ,1 });
	}
	while (!G_q.empty() || !R_q.empty()) {
		int G_size = G_q.size();
		int R_size = R_q.size();
		for (int k = 0; k < G_size; k++) {
			int x = G_q.front().x;
			int y = G_q.front().y;
			int t = G_q.front().t;
			G_q.pop();
			if (copy_map[x][y] == -1) continue;
			for (int i = 0; i < 4; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
					if (check_green[xx][yy] == 0 && (copy_map[xx][yy] == 1 || copy_map[xx][yy] == 2)) {
						check_green[xx][yy] = t + 1;
						G_q.push({ xx,yy,t + 1 });
						copy_map[xx][yy] = 3;
					}
				}
			}
		}
		for (int k = 0; k < R_size; k++) {
			int x = R_q.front().x;
			int y = R_q.front().y;
			int t = R_q.front().t;
			R_q.pop();
			for (int i = 0; i < 4; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
					if (check_red[xx][yy] == 0 && (copy_map[xx][yy] == 1 || copy_map[xx][yy] == 2)) {
						check_red[xx][yy] = t + 1;
						R_q.push({ xx,yy,t + 1 });
						copy_map[xx][yy] = 4;
					}
					else if (check_red[xx][yy] == 0 && copy_map[xx][yy] == 3) {
						if (check_green[xx][yy] == t + 1) {
							copy_map[xx][yy] = -1;
							check_red[xx][yy] = t + 1;
						}
					}
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (copy_map[i][j] == -1) flower++;
		}
	}
	answer = max(answer, flower);
}

void reset_map() {
	memset(check_green, 0, sizeof(check_green));
	memset(check_red, 0, sizeof(check_red));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copy_map[i][j] = map[i][j];
		}
	}
}

void select_red(int start, int cnt) {
	if (cnt == R) {
		bfs();
		reset_map();
	}
	else {
		for (int i = start; i < land.size(); i++) {
			if (check_land[land[i].first][land[i].second] == 1) continue;
			check_land[land[i].first][land[i].second] = 1;
			red.push_back(i);
			select_red(i, cnt + 1);
			red.pop_back();
			check_land[land[i].first][land[i].second] = 0;
		}
	}
}

void select_green(int start, int cnt) {
	if (cnt == G) {
		select_red(0, 0);
	}
	else {
		for (int i = start; i < land.size(); i++) {
			if (check_land[land[i].first][land[i].second] == 1) continue;
			check_land[land[i].first][land[i].second] = 1;
			green.push_back(i);
			select_green(i, cnt + 1);
			green.pop_back();
			check_land[land[i].first][land[i].second] = 0;
		}
	}
}

void solve() {
	select_green(0, 0);
	cout << answer;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> G >> R;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			copy_map[i][j] = map[i][j];
			if (map[i][j] == 2) land.push_back(make_pair(i, j));
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!