[알고리즘] 백준 14502번: 연구소 (C++), BFS와 Brute-force의 합작

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

14502번: 연구소

이 문제를 처음 보자마자 BFS를 떠올릴 수 있었지만 '제일 포인트가 되는 부분이 벽은 어떻게 세우지'가 고민거리였다.

하나하나 다 따지기엔 경우의 수가 너무 많아서 괜찮을까 싶었지만 주어진 평면의 크기는 8x8이라서 8^6(582144)로 큰 시간을 따지지는 않겠다는 생각이 들었다. (벽이 한 좌표에 몰빵 되는 경우도 계산한 것 >> 중복을 따지기엔 시간 계산에 너무 많은 시간을 쏟고 싶지 않았음.)

 

재귀 쪽보다는 브루트 포스 하면 떠올랐던 게 항상 많은 for문이었어서 for문을 사용했지만 6중 for문이 생기고 이는 따지지 않는 경우도 많았어서 논리적 오류가 발생한다.

---

재귀를 이용한 Brute-force

재귀를 이용해야겠다는 생각이 들어서 어떻게 할 지도 생각해보고, 다른 사람의 답도 참고해보았다.

생각했을 때는 벽이 3개 주어져야 하니까 벽이 생성되고, 3개가 되면 종료를 하고, 즉각적으로 BFS(바이러스 전염)를 한 다음 0인 구역을 카운트 한 뒤 다음 경우도 따져야 하므로 방문 여부 체크 배열과 입력 값 배열을 초기화시켜주는 작업이 필요했다.

 

하지만, 재귀를 이용한 코드마저도 따지지 않는 경우를 보여주었다.

1. 평면을 초기화시키는 작업(리셋 함수)의 위치가 문제인가
2. 벽을 고르는 함수가 문제인가

이 3가지를 중점적으로 디버깅을 해야 했다. (BFS 쪽은 문제가 없었다.)

 

[문제가 되었던 코드]

(디버깅용 출력들은 모두 주석 처리를 해놓은 상태에서 업로드를 한다.)

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

int n, m;
int map[9][9];
int map2[9][9];
bool visited[9][9];
int cnt;
int maxValue = 0;

typedef struct {
	int y, x;
}Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void bfs(int row, int col) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy <= n && dy >= 1 && dx <= m && dx >= 1) {
				if (map[dy][dx] == 0 && !visited[dy][dx]) {
					visited[dy][dx] = 1;
					q.push(make_pair(dy, dx));
					map[dy][dx] = 2;
				}
			}
		}
	}
}

void sol() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j] && map[i][j] == 2) {
				visited[i][j] = 1;
				bfs(i, j);
			}
		}
	}
}

void sol2() {
	// map print
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	*/

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) {
				cnt++;
			}
		}
	}
}

void visitedReset() {
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			visited[i][j] = 0;
		}
	}
}

void mapReset() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			map[i][j] = map2[i][j];
		}
	}
}

void makeWall(int wallCnt) {
	if (wallCnt == 3) {
		cnt = 0;
		sol(); // 전염
		sol2(); // 안전영역 탐색
		//cout << "안전영역 개수: " << cnt << '\n' << '\n';
		visitedReset();
		if (cnt > maxValue) {
			maxValue = cnt;
		}
		return;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				makeWall(wallCnt + 1);
				map[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> n >> m;

	int idx;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> idx;
			map[i][j] = idx;
			map2[i][j] = idx;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//cout << "i: " << i << " j: " << j << '\n';
			if (map[i][j] == 0) {
				map[i][j] = 1;
				makeWall(1);
				map[i][j] = 0;
			}
			visitedReset();
			mapReset();
		}
	}
				
	cout << maxValue;
	return 0;
}

---

디버깅

디버깅을 한 끝에 다음 TC에서 확인할 수 있었다.

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

벽을 세운 후, 전염시킨 다음에 평면과 안전 영역의 개수를 출력해보니 특이한 점을 발견할 수 있었다.

첫 번째 벽을 세우는 경우(main에서 벽을 세움)는 모든 경우를 다 따져나가는데 함수를 통해서 세워지는 벽들(2번째, 3번째)은 서로 번갈아가며 시작되는 부분에만 벽을 세우는 것을 알 수 있었다.

디버깅하는 중간에 방문 체크는 필요 없을 거 같아서 방문(visited) 관련 코드는 모두 지웠다.

참고한 포스팅을 따라서 오류가 어디서 발견될까 하며 하나씩 고치다가 100% 카피가 되었다.

(+참고 https://jaimemin.tistory.com/601)

 

카피를 하면서 들었던 생각은 아무래도 배열을 전염시키다 보니 전염시킬 배열을 따로 BFS 내에서 선언한 점

전염시키는 배열을 직접적으로 영향을 주다 보니 리셋을 시키는 함수가 필요했고, 이전에 벽을 세우는 기록 또한 세이브시키기 위해 코드를 스스로 꼬고 꼬면서 디버깅에 악영향을 주었다.

 

up-solving이 반드시 꼭 필요하다는 생각이 들었다. 벽을 3개 고르는 코드는 간단하지만 간단하게 사용하지 못했다는 점이 너무 아쉽게 다가왔다.

 

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

int n, m;
int temp[9][9];
int map[9][9];
int maxValue = 0;

typedef struct {
	int y, x;
}Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };


void bfs() {

	int afterSpread[9][9];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			afterSpread[i][j] = temp[i][j];
		}
	}

	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (afterSpread[i][j] == 2) {
				q.push(make_pair(i, j));
			}
		}
	}
	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy <= n && dy >= 1 && dx <= m && dx >= 1) {
				if (afterSpread[dy][dx] == 0) {
					q.push(make_pair(dy, dx));
					afterSpread[dy][dx] = 2;
				}
			}
		}
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (afterSpread[i][j] == 0) {
				cnt++;
			}
		}
	}

	if (maxValue < cnt) {
		maxValue = cnt;
	}
}

void makeWall(int wallCnt) {
	if (wallCnt == 3) {
		bfs(); // 전염, 안전 영역 탐색, 맵 프린트
		return;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (temp[i][j] == 0) {
				temp[i][j] = 1;
				makeWall(wallCnt + 1);
				temp[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> n >> m;

	int idx;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> idx;
			map[i][j] = idx;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) {
				for (int k = 1; k <= n; k++) {
					for (int l = 1; l <= m; l++) {
						temp[k][l] = map[k][l];
					}
				}
				temp[i][j] = 1;
				makeWall(1);
				temp[i][j] = 0;
			}
		}
	}
				
	cout << maxValue;
	return 0;
}

---

여러 가지 생각들이 간단하게 도출될 수 있지만 이 생각들을 엮는 데에 있어서도 간단하게 생각할 수 있게끔 코딩을 해야 한다고 느낀다. 

 

내 코드에 디버깅을 하려고 5~6시간 정도를 썼지만 리셋과 다음 리커시브들이 계속 얽혀있어서 파악해내지 못했다는 게 화도 나고 너무 아쉽다. 무조건 up-solving 해야 하는 문제다.