[BOJ] 18809 Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

문제

모든 경우의 수를 탐색해서 피울 수 있는 꽃의 최대 개수를 구한다.

 

 

 

 

풀이

 

백트래킹 + BFS이용해서 푼 문제

 

1. 먼저 배양액을 뿌릴 수 있는 땅 중에 초록색 배양액을 뿌릴 수 있는 땅을 선택한다.
2. 그 다음에 배양액을 뿌릴 수 있고 초록색 배양액이 뿌려지지 않은 땅 중 빨간색 배양액을 뿌릴 수 있는 땅을 선택한다. 
3. BFS 과정을 거쳐 배양액을 퍼뜨리고 핀 꽃의 개수를 세준다.

 

 

 

실수 했던 부분

• 백트래킹 과정에서 배양액을 뿌렸다가 회수해 주는 코드를 빼먹을 뻔 하였다.
• 배양액을 뿌려주는 과정에서 현재 탐색하는 땅이 이미 꽃을 피웠다면 넘어가는 부분에서 temp배열 대신 map배열로 비교하였다. 정말 집중 안하면 생기는 사소한 실수지만 이런 경우 꽃이 옆으로 퍼지는 현상이 일어났다. 이를 찾느라 시간을 덜 썼으면 한 문제 더 푼다.
• 인접한 땅에 꽃이 피워져 있는 경우, continue문을 실행해야 하는 부분에서 실수하기 쉽다.
• X, Y를 바꿔서 쓰거나 nextY와 currY를 바꿔서 쓰는 실수 주의한다.
• 가장 중요한건 문제 풀때 제대로 읽는 것이다. 급한 마음 가지지 말고 2번 읽는다.

 

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

pair<int, int> map[51][51];
pair<int, int> temp[51][51];
pair<int, int> possibleLand[10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int N, M, G, R, answer, landCnt;

//삼성 기출 문제는 꼭 복사하는 경우 많으니 잊지말고 실수하지 말기.
void copy() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			temp[i][j] = map[i][j];
		}
	}
}

int bfs() {
	int cnt = 0;
	queue<pair<int, int>> q;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j].first == 3 || map[i][j].first == 4) {
				q.push({ i,j });
			}
		}
	}
	
	int t = 0;
	while (!q.empty()) {
		t++;
		int sz = q.size();
		for (int i = 0; i < sz; i++) {
			pair<int, int> curr = q.front();
			q.pop();
			int currY = curr.first;
			int currX = curr.second;
			
			//꽃이 이미 핀 경우는 넘어간다
			//이렇게 특수한 경우를 잘 생각해야 한다.
			//그리고 map[currY][currX] 이렇게 실수했었으니 주의할것
			if (temp[currY][currX].first == 5) {
				continue;
			}

			for (int k = 0; k < 4; k++) {
				int nextY = currY + dy[k];
				int nextX = currX + dx[k];
				if (nextY < 1 || nextX < 1 || nextY > N || nextX > M) continue;
				if (temp[nextY][nextX].first == temp[currY][currX].first) continue;
				if (temp[nextY][nextX].first == 0) continue;

				//꽃이 있는 경우 넘어감 이런것도 놓치기 쉬우니 천천히 살펴볼것
				if (temp[nextY][nextX].first == 5) continue;
				

				//현재 초록색 배양액
				if (temp[currY][currX].first == 3) {
					if (temp[nextY][nextX].first == 4) {
						if (temp[nextY][nextX].second != t) continue;
						else {
							temp[nextY][nextX].first = 5;
							cnt++;
							continue;
						}
					}
				}
				//현재 빨간색 배양액
				else if (temp[currY][currX].first == 4) {
					if (temp[nextY][nextX].first == 3) {
						if (temp[nextY][nextX].second != t) continue;
						else {
							temp[nextY][nextX].first = 5;
							cnt++;
							continue;
						}
					}
				}

				//여기서 중요한건 currY와 currX를 착각했다.
				temp[nextY][nextX] = { temp[currY][currX].first, t };
				q.push({ nextY,nextX});
			}
		}	
	}

	return cnt;
}

void red(int depth, int num, int visited) {
	if (depth == R) {
		//여기까지 배양액 뿌리는 작업
		copy();
		answer = max(answer,bfs());
		return;
	}

	for (int i = num; i < landCnt; i++) {
		if (visited & (1 << i)) continue;
		pair<int, int> curr = possibleLand[i];
		map[curr.first][curr.second] = { 4, 0 };
		red(depth + 1, i + 1, visited | (1 << i));
		map[curr.first][curr.second] = { 2, 0 };
	}
}

void green(int depth, int num, int visited) {
	if (depth == G) {
		red(0, 0, visited);
		return;
	}

	for (int i = num; i < landCnt; i++) {
		if (visited & (1 << i)) continue;
		pair<int, int> curr = possibleLand[i];
		map[curr.first][curr.second] = { 3, 0 };
		green(depth + 1, i + 1, visited | (1 << i));
		map[curr.first][curr.second] = { 2, 0 }; //실수할 뻔한 포인트
	}
}

int main() {
	cin >> N >> M >> G >> R;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j].first;
			if (map[i][j].first == 2) {
				possibleLand[landCnt++] = { i,j };
			}
		}
	}

	//먼저 초록색 뿌릴 땅을 선택
	green(0, 0, 0);

	cout << answer;
}