백준 18809번 Gaaaaaaaaaarden

문제 링크:https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

[문제풀이]

 2차원 격자판에 배양액을 놓을 수 있는 칸, 없는 칸, 호수가 주어진다.

배양액을 놓을 수 있는 칸에 주어진 조건 만큼 배양액을 배치한다.

배양액은 동시에 퍼지기 시작하며, '색이 다른' 두 배양액이 동시에 퍼지는 순간 꽃이 핀다.

하지만 꽃이 피어난 땅은 배양액이 사라지기 때문에 더이상 인접한 땅으로 퍼지지 않는다.

주어진 조건에 맞게 시뮬레이션 했을 때 피울 수 있는 꽃의 최대 개수를 구한다.

 

문제 조건:

 

                  (1) 행과 열  N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50)

                  (2)  초록색 배양액의 개수 G(1 ≤ G ≤ 5)

                  (3) 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)

                  (4) 0은 호수, 1은 뿌릴 수 없는 땅, 2는 뿌릴 수 있는 땅

                  (5) 모든 배양액은 빠짐없이 사용해야 한다.

                  (6)  배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.

 

 

알고리즘 분석:

 

                   (1) 조합 

                   (2) BFS

 

(1) 조합

                  

재귀 함수를 통해 조합을 구현하면 된다.

"배열에서 배양액이 놓일 수 있는 위치를 벡터에 저장하고, 벡터의 크기만큼 조합을 구성"

신경써야 할 부분은 조합을 구현하되 두 개의 그룹으로 나누어지고 그 그룹도 조합으로 구성되어야 한다.

 

그림 1. (2,4,8) 선택했을 때

예를 들어 2,4,8 부분을 선택하였다고 가정해 보자.

시뮬레이션을 진행할 때 그룹을 순열로 구성 하였다고 한다면 초록색 2,4를 선택한 것과 4,2를 선택한 것은

다른 케이스로 생각하기 때문에 중복이 발생한다.

 

(2) BFS

 

매번 느끼지만 솔직히 이야기하면 bfs문제는 어느 정도 기본적인 패턴이 있다.

그렇기 때문에 "뭐야 이거 쉽잖아" 하면서 바로 키보드부터 뚜두리는데 그럼 바로 디버깅 지옥이다.

익숙하다고 느낄수록 문제 설계를 확실하게 해놓고 코딩에 들어가야 한다.

기본적인 설계를 해보면 이렇다.

 

1.  좌표의 위치, 배양액의 색, 시간을 큐에 넣는다.

2. bfs를 진행한다.

      1) 해당 좌표를 아직 방문하지 않았다면 색과 시간을 저장한다.

      2) 해당 좌표를 방문했다면

            i) 현재의 색과 이동해야하는 부분의 색이 같다면 continue.

            ii) 색이 다르다면   꽃의 개수를 하나 더해주고, 해당 좌표를 꽃 번호로 바꿔준다.

            ii) 이미 꽃이 피었다면 continue.

      3) 현재 큐의 좌표에서 이미 꽃이 피어있다면 continue.

 

아마 3)이 문제의 핵심이라는 생각이 든다. 저 부분을 퐉 생각 못해서 한참을 디버깅했다.

큐에 새로운 내용이 저장되는 때는 '아직 그 좌표를 방문하지 않았을 때'일 뿐이다.

       

요런 상황일 때, '?'부분에서 초록색 배양액도 2초, 빨간색 배양액도 2초에 저 좌표에서 마주치니깐

'이론상'  꽃이 피어야 한다. 

하지만 조건에서 '꽃이 피어난 땅은 배양액이 사라지기 때문에 더이상 인접한 땅으로 퍼지지 않는다' 고

했으므로 빨간색 배양액은 더 이상 퍼지면 안되기 때문에 '?' 자리에는 꽃이 피어선 안된다.

우연히 큐에 초록색 배양액이 먼저 들어갔다면 빨간색 배양액이 다음 좌표를 확인할 때 

"뭐야 꽃 피었네 그럼 큐에 안넣어야징"

이러면 전혀 문제가 되지 않지만 빨간색이 먼저 큐에 들어갔다면

"음.. 아직 아무도 오지 않았군 내 영역으로 만들고 큐에 넣어야지"

이미 큐에 들어갔기 때문에 그대로 진행되어서 '?'에 그.대.로 꽃이 핀다.

그럼 이걸 어떻게 해결할수 있을까?

정말 장담하건데 bfs문제는 많은 사람들이 A[ny][nx]에 집착한다.

다음 큐에 넣을 지 말지 고민하는 상황에서

그냥 어떻게는 다음 큐에 안들어가는 조건을 막 욱여넣어서 만들려고 하는 데  그럼 푸는데 8시간 걸린다.

그럼 심호흡하고 A[ny][nx]가 아니라 A[current_y][current_x]로 눈을 옮겨보자.

그저 여기서 다소곳하게 "웅? 큐에 들어왔는 데 꽃 핀 자리였네? 그럼 뭣하러봐 안봐" 하고 continue 박아 버리면 된다.

 

푸는 데 엄청 어려운 문제는 아니었다. 그리고 냉정하게 그렇게 시간도 오래 걸릴 문제도 아니었다.

대부분 몇시간 붙잡고 있으면 못 풀 문제는 확실히 아니다.

하지만 시간내에 못풀면 솔직히 의미가 없다.

 

"BFS문제 만나면 와 BFS다 개꿀! 하고 void BFS()부터 만들지말고 문제 꼼꼼히 읽고 설계부터하자"

 

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#define pii pair<int,int>
using namespace std;
int N, M, G, R,can_size, ans;
int A[50][50];
vector<pii> can;
vector<int> Gr, Re;
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
bool C[10];
struct info { int y, x; };
struct _b { int color, time; }B[50][50];

bool oob(int y, int x)
{
	if (y < 0 || y >= N || x < 0 || x >= M) return false;
	return true;
}

int bfs()
{
	int res = 0;
	memset(B, -1, sizeof(B));
	queue<info> Q;
	int y = 0, x = 0;
	for (auto p:Gr)
	{
		y = can[p].first, x = can[p].second;
		B[y][x] = { 0,0 };
		Q.push({ y, x });
	}
	for (auto p:Re)
	{
		y = can[p].first ,x = can[p].second;
		Q.push({ y, x });
		B[y][x] = { 1,0 };
	}
	while (!Q.empty())
	{
		int cy = Q.front().y;
		int cx = Q.front().x;
		int color = B[cy][cx].color;
		int ct = B[cy][cx].time;
		Q.pop();
		if (B[cy][cx].color==3) continue;
		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (!oob(ny, nx)||A[ny][nx]==0) continue;
			if (B[ny][nx].color == -1)
			{
				B[ny][nx].color = color;
				B[ny][nx].time = ct + 1;
				Q.push({ ny,nx,});
			}
			else if (B[ny][nx].color != 3)
			{
				if (B[ny][nx].color!=color&& B[ny][nx].time == ct + 1)
				{
					B[ny][nx].color = 3;
					res++;
				}
			}
		}
	}
	return res;
}

void go(int idx,int cnt,int g,int r)
{
	if (cnt > can_size) return;
	if (g > G) return;
	if (r > R) return;
	if (g == G && r == R) ans = max(ans, bfs());
	for (int i = idx; i < can_size; i++)
	{
		if (C[i]) continue;
		C[i] = true;
		Gr.push_back(i);
		go(i,cnt+1, g + 1, r);
		Gr.pop_back();
		Re.push_back(i);
		go(i, cnt+1,g, r + 1);
		Re.pop_back();
		C[i] = false;
	}
}

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", &A[i][j]);
			if (A[i][j] == 2) can.push_back({ i,j });
		}
	}
	can_size = can.size();
	go(0,0,0,0);
	printf("%d", ans);
}