[BackTracking] Gaaaaaaaaaarden C++

Seunghyeon·2023년 4월 8일

백준 문제 푼다.

목록 보기

16/21

풀이

황토색 토지에 들어갈 배양액들의 모든 경우의 수 구하기
BFS를 통해 배양액을 확산시키기

풀이는 상당히 간단해 보이지만 숨은 디테일들을 잘 살려서 풀어야 한다.

모든 경우의 수 구하기
-> 황토색 칸은 최대 10칸이다. 그 중 어느 칸에다가 빨간액, 초록액을 넣을지 정해야한다.

이 부분의 경우 처음에는 DFS 식으로 함수를 재귀 호출하여 완전탐색을 노렸는데
상당히 코드가 길어지고 필요한 변수들이 자꾸 하나씩 늘어감에 따라 큰 불편함을 느끼는 중
바킹독 선생님의 next_permutation 함수가 떠올랐다.

이 함수를 사용하면 굉장히 간편하게 모든 경우의 수를 찾게된다.

BFS를 통해 배양액 확산시키기
-> 2개의 배양액이 동시에 확산하는 모습을 구현해야하기 때문에 '깊이'를 정의해야 한다.

사실 두개의 큐를 돌리긴 힘드므로 시간이 지남에 따라 흔적을 남겨 동시에 두개의 도착을 알 수 있게 된다.

추가적으로 2개의 매개체를 돌릴때는 시간을 잘 확인해야 한다... 이 부분 때문에 상당히 막혔다.
큐 안에 꽃이 핀 곳으로의 배양액이 들어있을 수 있다. 그래서 큐에서 꺼낼때 마다 항상 확인을 해줘야 한다.
현재 꺼낸 배양액의 위치에 꽃이 폈는지 확인하는 것이다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef struct node {
	int x;
	int y;
};

int n, m, g, r;
int Max = 0;

// 사용할 순열 구하기용
int used[10];
int Map[51][51];
pair<int, int> state[51][51]; // 색깔, 시간

int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

vector<node> y;
queue<node> q;

void bfs()
{
	for (int i = 0; i < n; i++)
	{
		fill(state[i], state[i] + m, make_pair(0,-1));
	}

	// q에 값 넣기 ( used에 사용할 그거 나와있음 )
	for (int i = 0; i < y.size(); i++)
	{
		// green
		if (used[i] == 1)
		{
			state[y[i].x][y[i].y] = { 1,0 };
			q.push({ y[i].x, y[i].y });
		}
		else if (used[i] == 2)
		{
			state[y[i].x][y[i].y] = { 2,0 };
			q.push({ y[i].x, y[i].y });
		}
	}

	int flower = 0;

	// 빨간약,초록약이 뿌려진 위치가 담긴 큐에서 BFS 돌리기
	while (!q.empty())
	{
		int cx = q.front().x;
		int cy = q.front().y;
		int ccolor = state[cx][cy].first;
		int cdep = state[cx][cy].second;

		q.pop();

		// 현재 위치에 꽃이 폈다면
		if (state[cx][cy].first == 3) continue;

		for (int i = 0; i < 4; i++)
		{
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			int ndep = cdep + 1;

			// 호수거나 꽃이라면
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || Map[nx][ny] == 0 || state[nx][ny].first == 3)
				continue;

			// 아직 닿지 않은 곳이라면
			if (state[nx][ny].first == 0)
			{
				state[nx][ny].first = ccolor;
				state[nx][ny].second = ndep;
				q.push({ nx,ny });
			}
			// 꽃이 필 자리이면 (시간이 같고, 색깔이 다를 경우)
			else if (state[nx][ny].second == ndep && (state[nx][ny].first + ccolor == 3))
			{
				state[nx][ny] = make_pair(3, ndep);
				flower++;
			}
		}
	}

	Max = max(Max, flower);

	return;

}

// 하얀칸 : 배양액 못뿌림 , 황토칸 : 배양액 뿌릴수있 , 하늘색 : 호수
int main()
{
	cin >> n >> m >> g >> r;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// 0 : 호수, 1 : 흰색칸, 2 : 황토칸
			cin >> Map[i][j];

			if (Map[i][j] == 2)
			{
				y.push_back({ i,j });
			}
		}
	}

	int blanc = y.size() - g - r;

	fill(used + blanc, used + blanc + g, 1);
	fill(used + blanc + g, used + y.size(), 2);

	do {
		bfs();
	} while (next_permutation(used, used + y.size()));

	cout << Max;

	return 0;
}