[BOJ] 17142 : 연구소 3 - travelbeeee

문제 : https://www.acmicpc.net/problem/17142

---

[ 알고리즘풀이 ]

■ 연구소의 사이즈는 N, 바이러스의 개수는 M ( map을 입력받으면서 '0' 인 공간을 미리 count 해둔다. )

■ 바이러스를 M개 뽑아서 감염을 확산시킬 것이므로, 바이러스의 위치를 vir 에 저장한다.

■ Backtracking 을 이용해 vir에 저장된 바이러스 중 M개를 뽑는다.

■ 뽑힌 M개의 바이러스를 BFS 탐색을 이용해 감염을 확산시킨다. ( '0' 인 공간을 탐색하면 count )

 이때, 현재 Queue에 담겨있는(현재 탐색된 위치)가 모두 '2' 이고, 앞으로 탐색할 곳이 없다면 우리는 굳이 탐색하지 않아도 되는 비활성 바이러스들의 위치만 탐색한 것이므로, 탐색을 그전에 끝냈어야 한다. 따라서 time을 갱신하지 않고, BFS탐색을 break 한다. 그게 아닌 경우는 모두 감염이 진행되는데 필요한 시간이므로 time++ 을 통해 시간을 체크한다.

■ BFS 탐색을 하며 count 한 값과 (1) 에서 count 한 값을 비교해 모든 지역에 감염이 진행되었다면, 답을 갱신한다.

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#define INF 987654321

using namespace std;

vector<pair<int, int>> vir;
int N, M, spaceCount, ans = INF, map[50][50], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool choice[10];

void spreadVirus(void) {
	bool visited[50][50] = {};
	queue<pair<int, int>> q;
	for (int i = 0; i < vir.size(); i++)
		if (choice[i]){
			q.push({ vir[i].first, vir[i].second });
			visited[vir[i].first][vir[i].second] = 1;
		}
	int time = 0, cnt = 0;
	while (!q.empty()) {
		bool check1 = false, check2 = false;
		int s = q.size();
		for (int i = 0; i < s; i++) {
			pair<int, int> cur = q.front();
			q.pop();
			if (map[cur.first][cur.second] == 0)
				check1 = true;
			for (int j = 0; j < 4; j++) {
				int nextX = cur.first + dx[j], nextY = cur.second + dy[j];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
					if (map[nextX][nextY] != 1 && !visited[nextX][nextY]) {
						visited[nextX][nextY] = 1;
						check2 = true;
						q.push({ nextX, nextY });
						if (map[nextX][nextY] == 0)
							cnt++;
					}
				}
			}
		}
		if (check1 == false && check2 == false) // 기존에 다 '2'를 밟고, 지금은 밟은게 없다.
			break;
		else
			time++;
	}
	if (cnt == spaceCount)
		ans = min(ans, time);
	return;
}

void Backtracking(int s, int cnt) {
	if (cnt == M) {
		spreadVirus();
		return;
	}
	for (int i = s; i < vir.size(); i++) {
		choice[i] = true;
		Backtracking(i + 1, cnt + 1);
		choice[i] = false;
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				spaceCount++;
			if (map[i][j] == 2)
				vir.push_back({ i, j });
		}
	}

	if (spaceCount == 0)
		ans = 1;
	else
		Backtracking(0, 0);

	if (ans == INF)
		ans = 0;
	cout << ans - 1;
}

---