[BOJ C++] 백준 14502번: 연구소

 📚 문제

[BOJ C++] 백준 14502번: 연구소
https://www.acmicpc.net/problem/14502

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

조합(Backtracking)으로 벽을 세울 위치 3개를 선택하고, BFS(너비 우선 탐색)로 바이러스를 확산시키는 시뮬레이션을 결합하여 해결했다.

자세한 구현 방법은 다음과 같다.

1. 초기 위치 저장: 입력을 받으면서 빈칸(0)의 위치는 blank 벡터에, 바이러스(2)의 위치는 virusPos 큐에 별도로 저장한다. 빈칸은 나중에 벽을 세울 조합을 뽑기 위함이고, 바이러스는 BFS를 시작할 시작점들이기 때문이다.
2. 벽 세우기 (조합): blank 벡터에 저장된 좌표들 중 3개를 선택한다. 재귀 함수를 이용한 백트래킹 방식으로 구현하였으며, 벽을 세운 뒤(1) 재귀 호출이 끝나면 다시 없애는(0) 과정을 반복한다.
3. 바이러스 확산 (BFS): 벽이 3개 세워질 때마다 virus 함수를 호출한다. 초기 바이러스 위치들이 담긴 큐를 복사하여 상하좌우로 퍼뜨리며 빈칸의 개수를 줄여나간다.
4. 최댓값 갱신: 바이러스 확산이 끝난 후 남은 빈칸의 개수(blankCnt)를 계산하여 maxVal을 최댓값으로 갱신한다.

 

 💡 알고리즘 개선 및 최적화

두 가지 방법으로 성능을 높였다.

 

1. 가지치기 (Pruning)

시뮬레이션을 모두 구현한 후에 스스로 생각한 방법이다. 바이러스가 한 칸씩 퍼질 때마다 빈칸의 개수(blankCnt)를 1씩 줄여나가는데, 만약 남아 있는 빈칸의 수가 지금까지 구한 안전 구역의 최대 넓이(maxVal)보다 작거나 같아지면 나머지 빈칸이 모두 안전 구역이 되어도 최댓값이 될 수 없다. 즉, 더 이상 계산할 필요가 없으므로 즉시 함수를 종료(return)한다. 무의미한 값이므로 0을 리턴하였다.

 

2. 값에 의한 전달 vs 참조에 의한 전달

처음에는 combi 함수를 작성할 때 매개변수로 vector<vector<int>> board를 그대로 넘겨주는 값에 의한 전달(Call by Value) 방식을 사용했다. 이 부분을 개선할 방법이 있을 것 같아 AI에게 코드 리뷰를 맡겨본 결과, 이 방법은 재귀가 호출될 때마다 2차원 벡터가 통째로 복사되어 오버헤드 발생 위험이 있다는 것을 알 수 있었다. virus 함수에서만 바이러스가 퍼지는 시뮬레이션을 구현하면 되므로, combi 함수에서는 새로운 보드를 생성할 필요가 없다. 따라서 combi 함수에는 참조(&)를 전달하여 불필요한 복사를 방지하고, 실제 바이러스 전파 시뮬레이션이 일어나는 virus 함수 내부에서만 임시 보드를 복사하여 사용하는 방식으로 수정하였다.

 

---

 ⌨️ C++ 코드

/*
1. 입력 받으면서 빈칸, 바이러스 위치 별도로 저장.
	바이러스: 확산해야하므로 큐에 저장.
	빈칸: 조합으로 선택해야하므로 벡터에 저장.

2. 조합으로 3칸 선택, 벽 세우기
3. 바이러스 퍼지는 시뮬레이션 수행
4. 안전 영역 크기 계산

위 2~4단계 반복.
*/

#include<bits/stdc++.h>
using namespace std;

struct Cell {
	int r, c;
	Cell(int r, int c) : r(r), c(c) {}
};

void combi(vector<vector<int>>&, int, int);
int virus(vector<vector<int>>&);

vector<Cell> blank; // 빈칸 위치 저장.
queue<Cell> virusPos; // 바이러스 위치 저장.

int dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 }, n, m, maxVal = 0;

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> n >> m;
	vector<vector<int>> board(n, vector<int>(m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0)
				blank.emplace_back(i, j);
			else if (board[i][j] == 2)
				virusPos.emplace(i, j);
		}
	}
	combi(board, 0, 0);
	cout << maxVal;
}

// 수정: combi 함수에서는 board를 사용하지 않음. (virus 함수로 전달하기 용.)
// -> 값으로 전달하는 대신 참조(&)를 전달하고, virus 함수 내에서 board를 복사하여 사용.
void combi(vector<vector<int>> &board, int start, int cnt) {
	if (cnt == 3) {
		maxVal = max(maxVal, virus(board));
		return;
	}

	for (int i = start; i < blank.size(); i++) {
		board[blank[i].r][blank[i].c] = 1;
		combi(board, i + 1, cnt + 1);
		board[blank[i].r][blank[i].c] = 0; // 되돌리기.
	}
}

int virus(vector<vector<int>> &originBoard) {
	vector<vector<int>> board = originBoard; // 넘겨 받은 원본 board를 복사하여 사용.
	queue<Cell> q = virusPos;
	int blankCnt = blank.size() - 3;

	while (!q.empty()) { // 바이러스 확산.
		Cell cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cur.r + dr[i], nc = cur.c + dc[i];
			if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
			if (board[nr][nc] != 0) continue;
			board[nr][nc] = 2;
			blankCnt--;

			// 빈칸의 수가 지금까지 구한 최대 안전 영역크기보다 작으면 가지치기.
			if (blankCnt <= maxVal) return 0;

			q.emplace(nr, nc);
		}
	}
	return blankCnt;
}