Syureu

찍먹을 좋아하는 사람.

BOJ 18809 Gaaaaaaaaaarden

8 분 소요

1번을 원트에 풀어서 생각보다는 순조로웠다. 삼성 역량테스트 A형 유형을 흉내를 냈다면 이 문제는 상대적으로 어려운 “상황을 구성하고 그 상황에서 탐색을 하는” 문제인 것을 미리 생각하고 읽어 봤다.

용어 정리

맵 : n * m의 지도 데이터(int v[50][50])

문제 분석

  1. 맵에 호수, 그냥 땅, 배양액을 뿌릴 수 있는 땅이 각각 0, 1, 2로 주어진다
  2. g 만큼의 녹색 배양액과 r 만큼의 적색 배양액을 받는다.
  3. 배양액을 뿌릴 수 있는 땅에만 배양액을 하나만 뿌릴 수 있다.
  4. 배양액은 1초에 상하좌우 한칸씩 퍼져 나간다. 다만 호수, 다른 배양액이 이미 있는 경우, 꽃이 있는 경우는 불가능하다. 즉 배양액을 뿌릴 수 있지만 안뿌린 자리와 그냥 땅에만 퍼져 나간다는 것이다.
  5. r, g배양액이 동시에(같은 초에) 같은 칸으로 퍼지는 순간 꽃이 된다. 꽃이 되면 배양액은 없어지고 더 이상 그 칸을 지나서 퍼질 수 없다.
  6. 주어진 조건에 따라 배양액을 뿌려보고 꽃의 개수 최대값을 구하라.

삼성 역량테스트 A형의 “어려운” 유형에 잘맞는 문제이면서 좀 어려웠다. 나는 포스팅 시점 기준 A형을 실제로 쳐본적이 없어서 기출이 복기된 문제들만 풀어봤는데, 구현을 너무 어렵게 만드는 문제들이 있었던 것 같다. 이 문제는 구현 난이도가 아주 어렵진 않으나 좀 있으면서 역테 트렌디함을 잘 갖춘 문제같다.
내가 말하는 이 “어려운” 문제의 트렌디함이 다음과 같다.

  • 문제에서 상황이 주어지고, 구성할 수 있는 모든 상황에서 탐색 혹은 시뮬레이션을 하여 어떤 결과, 최댓값, 최솟값 등을 도출

이 문제도 잘 보면 배양액을 뿌릴 수 있는 상황(경우의 수)가 여럿 만들어짐을 알 수 있다. 그러한 여러 경우의 수 중 꽃이 피는 최댓값을 찾아야 한다.

접근

  1. 우선 배양액을 뿌릴 수 있는 공간을 선택해야 한다.
    문제에서 배양액을 뿌릴 수 있는 땅이 r + g 이상으로 주어진다. 딱맞게가 아니라. 다만 제한은 r + g가 최대 10이므로 10 C r+g 이다.

  2. 배양액을 뿌릴 땅이 선택 되었으면 r과 g 배양액을 각각 어디에 뿌릴 지 결정해야 한다.
    경우는 r+g C r 혹은 r+g C g이다. 땅이 r + g 만큼 선택 되었고, 그중 r개를 골랐다면 나머지는 g가 그냥 들어갈 수 밖에 없다.

  3. r, g가 놓일 공간이 결정 되었다면 bfs로 시뮬레이션 한다.
    우선 배양액이 퍼져나가는 것과 퍼져나간 시간에 따라 처리된다는 것 때문에 bfs로 탐색을 했다. dfs의 경우 어떤 지점까지의 도착 최소 시간(최소 거리)를 구할 수는 있지만 매우 비효율적이고 백트래킹을 시켜야 최소지점이 잘 구해지게 되므로 중복방문이 매우 많이 발생, n, m이 커지면 걷잡을 수 없다.

  4. 꽃의 갯수를 카운팅해서 최대값이면 갱신

접근은 1234만 보면 쉬워보이지만 구현이 좀 어려웠다.

1. 배양액을 뿌릴 수 있는 공간 선택

// struct A { int a, x, y; };
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
    cin >> v[i][j];
    if (v[i][j] == 2) water.push_back({ k++,i,j });
}

배열을 입력 받다가 배양액을 뿌릴 수 있는 공간이면 카운팅을 했다. 이 부분은 이미지로 보여주는게 설명하기 편할 듯?

vector<int>rand_choicer(water.size());
for (int i = 0; i < g + r; ++i) rand_choicer[i] = 1;

이제 어느 땅에다가 뿌릴 지 골라야 하는데 permutation으로 조합을 만드는 트릭을 사용했다.
배양액을 뿌릴 수 있는 땅을 우리는 바로 위에서 번호를 매겨놨다. 그중 어떤 번호를 고르겠다면 1, 고르지 않겠다면 0으로 나타내는 것이다.

2. 배양액을 뿌리기로 한 땅에 어떤 배양액을 뿌릴지 선택

vector<char>seq;
for (int i = 0; i < g; ++i) seq.push_back('g');
for (int j = 0; j < r; ++j) seq.push_back('r');

문제 풀이 가장 앞서서 이러한 seq 배열을 만들어 주는데, g = 2, r = 1과 같은 식이면 seq[0] = ‘g’, seq[1] = ‘g’, seq[2] = ‘r’ 와 같은 상태로 초기화 시켜준다. 이 배열의 의미는 배양액 뿌릴 수 있는 칸 0번은 g를 뿌리고 1번은 g를 뿌리고 2번엔 r을 뿌리겠다는 의미이다. next_permutation을 돌려주면 grg 순으로 변경되므로(g가 r보다 아스키 값이 작으니) next_permutation 있는 만큼 돌려보면 모든 g와 r을 뿌리는 경우의 수를 만들 수 있다.

3. bfs 시뮬레이션

do {
	do {
		C visit[50][50] = { \0 };
		tmp = 0;
		queue<B>q;
		int choicenum = -1;
		while (1) if (rand_choicer[++choicenum])break;
		for (int i = 0; i < g + r; ++i) {
			q.push({ seq[i],0,water[choicenum].x,water[choicenum].y });
			if (seq[i] == 'g') visit[water[choicenum].x][water[choicenum].y].color += 1;
			else if (seq[i] == 'r') visit[water[choicenum].x][water[choicenum].y].color += 2;
			if(i!=g+r-1) while (1) if (rand_choicer[++choicenum])break;
		}
		while (!q.empty()) {
			B b = q.front(); q.pop();
			if (visit[b.x][b.y].color == 4) continue;
			for (int i = 0; i < 4; ++i) {
				int nx = b.x + dx[i], ny = b.y + dy[i];
				if (0 <= nx && nx < n && 0 <= ny && ny < m) {
					if (!v[nx][ny]) continue;
					if (visit[nx][ny].color == 4) continue;
					if (!visit[nx][ny].color) {
						q.push({ b.color,b.depth + 1,nx,ny });
						if (b.color == 'g') visit[nx][ny].color += 1;
						else if (b.color == 'r') visit[nx][ny].color += 2;
						visit[nx][ny].depth = b.depth + 1;
					}
					else if (visit[nx][ny].color == 1 && b.color == 'r' && b.depth+1 == visit[nx][ny].depth) {
						visit[nx][ny].color = 4;
						tmp++;
					}
					else if (visit[nx][ny].color == 2 && b.color == 'g' && b.depth+1 == visit[nx][ny].depth) {
						visit[nx][ny].color = 4;
						tmp++;
					}
				}
			}
		}
		if (ans < tmp) ans = tmp;
	} while (next_permutation(seq.begin(), seq.end()));
} while (prev_permutation(rand_choicer.begin(), rand_choicer.end()));

아.. 코드만 봐도 현자타임이 진하게 온다
하나씩 뜯어 보자.

  1. 가장 바깥 do while은 rand_choicer를 돌린다.
    아까 우리는 이렇게 1로 뿌릴 곳 0으로 안뿌릴 곳을 선택하기 위한 배열을 만들어 뒀다.
    그리고 내림차순 순열을 돌리기 때문에 11100, 11010, 11001, … , 00111 까지 배양액을 뿌릴 수 있는 땅 중에서 어떤 땅을 고를지 모든 경우의 수를 만들 수 있다.

  2. 그 바로 안 do while은 g, r 배양액이 각각 놓일 위치를 돌려준다.
    마찬가지로 gggrr, ggrgr, ggrrg, … , rrggg 까지 모든 경우를 만들 수 있다.

  3. 이제 모든 상황이 구성되었으므로 시뮬레이션 하는 부분이다.
    visit는 두개의 int로 된 C 구조체를 사용했다. 이 문제는 단순히 방문만 처리하면 되는게 아니다.
    한 큐로 bfs를 돌리기 때문에 시뮬레이션 상 같은 지점에 동시에 g, r배양액이 퍼지는 것을 나타 낼 수가 없다.

    즉 g 배양액이 퍼지는 것에 대한 처리가 되고나면, r 배양액이 퍼지는 것에 대한 처리가 순서대로 일어난다. (초기 큐에 넣어준 순서에 따라) 그래서 만약 방문만 했다는 정보만 가지고 있다면 해당 배양액이 언제 그 칸에 도착했는지 모르기 때문에 다른 배양액이 그 칸에 접근 헀을 때 꽃이 될지, 혹은 시간이 달랐기 때문에 접근 할 수 없는지 알 수가 없다는 말이다.
    이러한 문제를 해결하기 위해 우리는 방문지점에 방문사실을 나타내면서 그 방문이 몇 초에 이루어 졌는지를 나타낼 것이다! 그게 C 구조체의 depth 변수가 할 역할이다.

  4. bfs 돌리기 위한 시작 포인트를 넣어준다.
/*
struct B {
	char color;
	int depth, x, y;
};
*/
queue<B>q;
int choicenum = -1;
while (1) if (rand_choicer[++choicenum])break;
for (int i = 0; i < g + r; ++i) {
    q.push({ seq[i],0,water[choicenum].x,water[choicenum].y });
    if (seq[i] == 'g') visit[water[choicenum].x][water[choicenum].y].color += 1;
    else if (seq[i] == 'r') visit[water[choicenum].x][water[choicenum].y].color += 2;
    if(i!=g+r-1) while (1) if (rand_choicer[++choicenum])break;
}

choicenum은 rand_choicer에서 인덱스를 나타내기위해 썼다. 우리는 1을 배양액 뿌릴 땅, 0을 배양액 안뿌릴 땅으로 골랐기 때문에 1만 가리키도록 해줬다.
그리고 방문을 나타내는 곳에 내 나름의 규칙을 세웠는데.

  • g 배양액이 방문한 곳은 C.color에 1을 쓴다.
  • r 배양액이 방문한 곳은 C.color에 2를 쓴다.
  • 꽃이 핀 곳은 C.color에 4를 쓴다.

원래는 비트마스킹하려고 해서 1, 2, 3을 할려고 했는데 왜 이렇게 된거지..

셋팅 다된 bfs가 실제로 도는 부분

while (!q.empty()) {
	B b = q.front(); q.pop();
	if (visit[b.x][b.y].color == 4) continue;
	for (int i = 0; i < 4; ++i) {
		int nx = b.x + dx[i], ny = b.y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if (!v[nx][ny]) continue;
			if (visit[nx][ny].color == 4) continue;
			if (!visit[nx][ny].color) {
				q.push({ b.color,b.depth + 1,nx,ny });
				if (b.color == 'g') visit[nx][ny].color += 1;
				else if (b.color == 'r') visit[nx][ny].color += 2;
				visit[nx][ny].depth = b.depth + 1;
			}
			else if (visit[nx][ny].color == 1 && b.color == 'r' && b.depth+1 == visit[nx][ny].depth) {
				visit[nx][ny].color = 4;
				tmp++;
			}
			else if (visit[nx][ny].color == 2 && b.color == 'g' && b.depth+1 == visit[nx][ny].depth) {
				visit[nx][ny].color = 4;
				tmp++;
			}
		}
	}
}

순서대로 보자.

  1. 큐를 깐다
  2. 지금 지점이 꽃이면 배양액이 지나서 퍼질 수 없기 때문에 스킵한다
  3. 4방지점을 탐색하는데 맵 범위 안이면서
    • v[nx][ny] == 0 이라면 (호수 라면) 스킵
    • visit[nx][ny].color == 4 라면 (꽃이라면) 스킵
  4. 그외 스킵이 안됐으면 다음과 같은 사항을 확인해 보는데
    visit[nx][ny].color == 0 이라면 (g도 r도 꽃도 없는 곳이라면)

    지금 도착한 배양액으로 이칸을 덮어준다. depth도 퍼지기 전 배양액 +1로 기록

    visit[nx][ny].color ==1 이면서 (여기 g 배양액이 방문했으면서)
b.color =='r' 이면서 (나는 r 배양액 이면서)
b.depth+1 == visit[nx][ny].depth 이면 (내가 퍼졌을 때의 시간과 그 자리에 배양액이 퍼진 시간이 같으면)

    위 세가지 조건을 만족하면 같은 칸에 같은 시간에 r, g 배양액이 접근한 것으로 보고 꽃을 만든다.
    (visit[nx][ny].color = 4)
    그리고 tmp는 현재 상황의 꽃의 갯수를 나타내는데 꽃이 만들어 졌으므로 tmp++
    방금은 g 배양액이 간 곳에 r 이 접근한 상황이므로 반대의 것도 만들어 주면 된다.

  5. 큐가 비었으면 돌 수 있는곳 다돌았다는 것으로 tmp가 최댓값이라면 ans 갱신

끝!

소스

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, g, r, v[50][50], ans, tmp,
dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
struct A {
	int a, x, y;
};
struct B {
	char color;
	int depth, x, y;
};
struct C {
	int color, depth;
};
vector<A>water;
void go() {
	vector<char>seq;
	for (int i = 0; i < g; ++i) seq.push_back('g');
	for (int j = 0; j < r; ++j) seq.push_back('r');
	vector<int>rand_choicer(water.size());
	for (int i = 0; i < g + r; ++i) rand_choicer[i] = 1;
	do {
		do {
			C visit[50][50] = { \0 };
			tmp = 0;
			queue<B>q;
			int choicenum = -1;
			while (1) if (rand_choicer[++choicenum])break;
			for (int i = 0; i < g + r; ++i) {
				q.push({ seq[i],0,water[choicenum].x,water[choicenum].y });
				if (seq[i] == 'g') visit[water[choicenum].x][water[choicenum].y].color += 1;
				else if (seq[i] == 'r') visit[water[choicenum].x][water[choicenum].y].color += 2;
				if(i!=g+r-1) while (1) if (rand_choicer[++choicenum])break;
			}
			while (!q.empty()) {
				B b = q.front(); q.pop();
				if (visit[b.x][b.y].color == 4) continue;
				for (int i = 0; i < 4; ++i) {
					int nx = b.x + dx[i], ny = b.y + dy[i];
					if (0 <= nx && nx < n && 0 <= ny && ny < m) {
						if (!v[nx][ny]) continue;
						if (visit[nx][ny].color == 4) continue;
						if (!visit[nx][ny].color) {
							q.push({ b.color,b.depth + 1,nx,ny });
							if (b.color == 'g') visit[nx][ny].color += 1;
							else if (b.color == 'r') visit[nx][ny].color += 2;
							visit[nx][ny].depth = b.depth + 1;
						}
						else if (visit[nx][ny].color == 1 && b.color == 'r' && b.depth+1 == visit[nx][ny].depth) {
							visit[nx][ny].color = 4;
							tmp++;
						}
						else if (visit[nx][ny].color == 2 && b.color == 'g' && b.depth+1 == visit[nx][ny].depth) {
							visit[nx][ny].color = 4;
							tmp++;
						}
					}
				}
			}
			if (ans < tmp) ans = tmp;
		} while (next_permutation(seq.begin(), seq.end()));
	} while (prev_permutation(rand_choicer.begin(), rand_choicer.end()));
}
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> g >> r;
	int k = 0;
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
		cin >> v[i][j];
		if (v[i][j] == 2) water.push_back({ k++,i,j });
	}
	go();
	cout << ans;
}

참고