17142 연구소3

 

17142번: 연구소 3

이번 문제는 간단히 정리하면

M개 이상 10개 이하의 임의의 지점을 선택해서 탐색을 진행했을 때에 모든 방을 탐색하는 것에 소요되는 최소 시간을 구하는 문제이다.

 

먼저 탐색 공간의 크기가 최대 50 X 50이고 바이러스는 최대 10개이기에 전역 탐색을 진행해도 빠르게 끝낼 수 있다고 판단되어 next_permutation 함수를 사용해서 바이러스를 활성화하는 모든 경우의 수를 탐색하였다.

그리고 활성화 바이러스는 인접한 지역으로 동시에 퍼지므로 사용한 알고리즘은 BFS를 선택하였으며 당연히 자료구조는 queue를 사용하였다. queue에는 매 시간마다 새롭게 바이러스가 전파하는 지점을 집어넣어 주었으며, 중복 탐색을 막기 위해서 탐색이 진행된 공간은 모두 벽으로 처리하였다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
using mypair = pair<int, int>;

int lab[50][50];

vector<pair<int, int>> virus;
vector<bool> flags;

int N, M;
int min_time = 987654321;
mypair steps[4] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void BFS(int space) {
	queue<mypair> q;

	for (int i = 0; i < flags.size(); ++i) {
		switch (flags[i]) {
		case 0:
			lab[virus[i].first][virus[i].second] = 3;
			break;
		case 1:
			q.push(virus[i]);
			lab[virus[i].first][virus[i].second] = 2;
			break;
		}
	}
	int copy[50][50];
	memcpy(copy, lab, sizeof(lab));

	int time = 0;
	while (!q.empty()) {
		if (!space) {
			min_time = min(time, min_time);
			return;
		}
		int size = q.size();
		++time;

		for (int i = 0; i < size; ++i) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();

			for (int j = 0; j < 4; ++j) {
				int next_x = x + steps[j].second;
				int next_y = y + steps[j].first;
				if (next_x < N && next_x >= 0 &&  next_y  < N && next_y >= 0) {
					switch (copy[next_y][next_x]) {
					case 0:
						--space;
						copy[next_y][next_x] = 1;
						q.push({ next_y, next_x });
						break;
					case 3:
						copy[next_y][next_x] = 1;
						q.push({ next_y, next_x });
						break;
					}
				}
			}
		}
	}
	return;
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> M;

	int space = 0;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> lab[i][j];
			switch (lab[i][j]) {
			case 0:
				++space;
				break;
			case 2:
				virus.push_back({ i, j });
				flags.push_back(false);
				break;
			}
		}
	}
	fill(flags.begin(), flags.begin() + M, true);
	sort(flags.begin(), flags.end());
	do {
		BFS(space);
	} while (next_permutation(flags.begin(), flags.end()));

	if (min_time == 987654321) {
		cout << -1;
	}
	else {
		cout << min_time;
	}
	return 0;
}