[G1] 백준 18809번 Gaaaaaaaaaarden C++ 백트래킹, 너비 우선 탐색, 해시맵

리뷰

 

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

여러가지 자료구조와 알고리즘을 결합하여 푼 문제

 

 

전역 변수

1. N, M : 맵의 세로/가로 길이를 저장할 변수
2. G, R : 초록/빨간색 배양액의 개수를 저장할 변수
3. ans : 정답을 저장할 변수
4. lst : 초기 맵 정보를 저장할 배열
5. Gs, Rs : 초록/빨간색 배양액을 뿌릴 땅의 인덱스를 저장할 벡터
6. Pos : 시뮬레이션 시 위치 x, y와 배양액의 색 c를 정의할 구조체
7. land : 배양액을 뿌릴 수 있는 땅의 개수
8. lands : 배양액을 뿌릴 수 있는 땅의 개수를 저장할 Pos타입의 배열
9. landsV : 땅의 인덱스를 기준으로 방문처리를 진행할 배열
10. dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bt

void bt(int Gc, int Rc)

 

백트래킹을 통해 배양액을 뿌릴 수 있는 모든 조건을 구하는 함수

매개 변수로 초록/빨간색 배양액을 뿌린 횟수 Gc, Rc를 전달 받는다.

기저 조건으로 Gc가 G이고, Rc가 R인 경우 floodfill함수를 호출하여 받은 리턴값과 ans중 큰 값으로 갱신 후 리턴한다.

Gc가 G보다 작을 경우 방문하지 않은 땅을 골라 해당 인덱스를 Gs에 push해준다.

Gc를 1만큼 증가시킨 후 재귀를 진행하고, 재귀를 빠져나오면 방문 해제와 Gs에서 마지막 요소를 pop해준다.

Rc가 R보다 작을 경우 방문하지 않은 땅을 골라 해당 인덱스를 Rs에 push해준다.

Rc를 1만큼 증가시킨 후 재귀를 진행하고, 재귀를 빠져나오면 방문 해제와 Rs에서 마지막 요소를 pop해준다.

 

2. floodfill

int floodFill()

 

배양액을 퍼트려 피울 수 있는 꽃의 개수를 구하는 함수

Pos 타입의 큐 q1을 초기화 한다.

key : 좌표, value : 배양액/꽃 정보를 담을 해시맵 spread를 초기화 한다.

2차원 정수형 벡터 temp에 lst벡터를 복사해 준다.

Gs를 순회하며 q1에 초록색 배양액를 퍼뜨릴 땅 정보를 push하고, temp에 초록색 배양액을 칠해준다.

Rs를 순회하며 q1에 빨간색 배양액를 퍼뜨릴 땅 정보를 push하고, temp에 빨간색 배양액을 칠해준다.

꽃의 개수를 저장할 변수 F를 0으로 초기화 하고, q1이 빌 때 까지 while루프를 수행한다.

Pos타입의 큐 q2를 초기화 하고, swap을 통해 q1와 q2를 바꾸어준다.

q2가 빌 때 까지 while문을 실행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.

4방향 탐색을 진행하고, 이동할 위치가 temp상에서 1인 경우 이동을 진행한다.

변수 idx에 2차원 맵 정보를 정수 한개로 매핑해 해시 맵 spread의 key로 활용해 준다.

만약 spread의 idx가 비어있다면 cc를 해당 값에 저장해 준다.

만약 spread의 idx가 cc와 다르다면 해당 값에 꽃이 폈음을 의미하는 정수로 저장해 준다.

위 두 사항에 해당하지 않는다면 continue처리해 준다.

while루프가 종료된 후 spread를 돌아 꽃이 핀 경우 F를 증가시켜 준다.

배양액만 칠해진 경우 q1에 다시 해당 위치와 배양액 정보를 push해준다.

모든 탐색을 마친 후엔 F에 저장된 값을 리턴해 준다.

 

3. print

void print(const vector<vector<int>>& temp) {
	cout << "\n";
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cout << temp[i][j] << " ";
		}
		cout << "\n";
	}
}

 

디버깅용 함수

 

 

문제풀이

1. N, M, G, R에 각각의 값을 입력 받고, lst를 N * M 크기로 resize해준다.
2. N * M 크기의 맵 정보를 입력 받고, 2가 입력된 경우 lands배열에 위치를 기록 후 1로 변경해 준다.
3. bt함수에 매개변수 0, 0을 전달하여 백트래킹을 수행해 준다.
4. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 예제가 정확하게 출력되지 않아 문제를 다시 확인해 보니 호수의 값이 1이 아닌 0이었다.
2. 백트래킹 내부에서 초록/빨간색 배양액을 선택하는 각각의 경우를 for문으로 돌렸더니 시간 초과가 발생했다.
3. if, else문으로 변경해 주었더니 느리지만 AC를 받게 되었다.

 

참고 사항

• 직접 복사한 맵에 기록하지 않고 해시맵 하나 만으로도 시뮬레이션을 돌릴 수 있어 보인다.
• 다른 사람들의 정답 제출이 300ms 언저리 인걸 보니 4배정도 더 빠르게 돌릴 수 있는 최적화 방안이 있다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

int N, M, G, R, ans;
vector<vector<int>> lst;
vector<int> Gs, Rs;
struct Pos {
	int x, y, c;
};
int land;
Pos lands[10];
bool landsV[10];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void print(const vector<vector<int>>& temp) {
	cout << "\n";
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cout << temp[i][j] << " ";
		}
		cout << "\n";
	}
}

int floodFill() {
	queue<Pos> q1;
	unordered_map<int, int> spread;
	vector<vector<int>> temp = lst;

	for (int i : Gs) {
		q1.push({ lands[i].x, lands[i].y, 3 });
		temp[lands[i].x][lands[i].y] = 3;
	}
	for (int i : Rs) {
		q1.push({ lands[i].x, lands[i].y, 4 });
		temp[lands[i].x][lands[i].y] = 4;
	}
	
	int F = 0;
	while (!q1.empty()) {
		//print(temp);
		queue<Pos> q2;
		swap(q1, q2);
		while (!q2.empty()) {
			Pos pos = q2.front(); q2.pop();
			int cx = pos.x, cy = pos.y, cc = pos.c;

			for (int i = 0; i < 4; ++i) {
				int nx = cx + dx[i], ny = cy + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < M && temp[nx][ny] == 1) {
					int idx = nx * M + ny;
					if (!spread[idx]) spread[idx] = cc;
					else if (spread[idx] != cc) spread[idx] = 5;
					else continue;
				}
			}
		}
		for (const auto& d : spread) {
			int x = d.first / M, y = d.first % M;
			temp[x][y] = d.second;
			if (d.second != 5) q1.push({ x, y, d.second });
			else F++;
		}
		spread.clear();
	}
	return F;
}

void bt(int Gc, int Rc) {
	if (Gc == G && Rc == R) {
		ans = max(ans, floodFill());
		return;
	}
	if (Gc < G) {
		int def = 0;
		if (!Gs.empty()) def = Gs.back();
		for (int i = def; i < land; ++i) {
			if (landsV[i]) continue;
			landsV[i] = 1;
			Gs.push_back(i);
			bt(Gc + 1, Rc);
			landsV[i] = 0;
			Gs.pop_back();
		}
	}
	else if (Rc < R) {
		int def = 0;
		if (!Rs.empty()) def = Rs.back();
		for (int i = def; i < land; ++i) {
			if (landsV[i]) continue;
			landsV[i] = 1;
			Rs.push_back(i);
			bt(Gc, Rc + 1);
			landsV[i] = 0;
			Rs.pop_back();
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> G >> R;
	lst.resize(N, vector<int>(M));

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> lst[i][j];
			if (lst[i][j] == 2) {
				lands[land++] = { i, j };
				lst[i][j] = 1;
			}
		}
	}
	bt(0, 0);
	cout << ans;
}