[BOJ] #17142 _ 연구소3

[연구소3] https://www.acmicpc.net/problem/17142

17142번: 연구소 3

조합을 이용한 문제로, 3개의 바이러스를 선택하여 가장 빠르게 퍼트리는 방법을 구현하는 문제이다.

dfs를 이용하여 조합을 구할 수 있지만, next_permutation을 이용하여 간단히 구현하였다.

코드의 동작 순서는 다음과 같다.

 

1. 처음 연구소의 상태를 lab배열에 저장하고, 선택된 바이러스를 -1로 변경한다.

2. bfs를 이용하여 퍼지는데 걸리는 최대 시간을 체크한다.

3. checkInfection() 함수를 이용하여 모든 지점에 바이러스가 퍼졌는지 확인한다.
-> 바이러스를 퍼트린후 남아있는 0의 개수를 카운트하여,
바이러스의 수보다 많으면 바이러스가 퍼지지 않은 것으로 판단하였다.

4. 모든 조합을 다 돌리면서 바이러스를 퍼트릴 수 있는 최단 시간을 구한다.
(이 때, 주의 할 점은 비활성 바이러스가 있던 구간은 시간을 체크할 때 포함하지 않아야 한다.)

 

[ 소스 코드 ]

#include <cstdio>
#include <queue>
#include <algorithm>
#define MAX 51
#define INF 999999999

using namespace std;

int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int n, m, min_time = INF;
int lab[MAX][MAX], tmp[MAX][MAX];
vector<pair<int, int> > virus;
vector<int> v;

void solve();
int infectVirus();
int checkInfection();
void copyLab();
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &lab[i][j]);
			if (lab[i][j] == 2) virus.push_back(make_pair(i, j));
		}
	}

	solve();
	if (min_time == INF) printf("-1\n");
	else printf("%d\n", min_time);

	return 0;
}

void solve() {
	int tmp_min;
	for (int i = 0; i < virus.size(); i++) {
		if (i < m) v.push_back(0);
		else v.push_back(1);
	}

	do {
		copyLab();
		tmp_min = infectVirus();
		if (checkInfection()) min_time = min(min_time, tmp_min);
	} while (next_permutation(v.begin(), v.end()));
}

int infectVirus() {
	int tmp_y, tmp_x, y, x, val = 0;
	queue<pair<int, int> > q, re_q;

	for (int i = 0; i < v.size(); i++) {
		if (!v[i]) {
			lab[virus[i].first][virus[i].second] = -1;
			q.push(virus[i]);
			re_q.push(virus[i]);
		}
		tmp[virus[i].first][virus[i].second] = 0;
	}

	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			tmp_y = y + dy[i];
			tmp_x = x + dx[i];
			if (tmp_x < 0 || tmp_y < 0 || tmp_x >= n || tmp_y >= n) continue;
			if (lab[tmp_y][tmp_x] == 1) continue;
			if (lab[tmp_y][tmp_x] == -1) continue;
			if (tmp[tmp_y][tmp_x] != 0) continue;
			tmp[tmp_y][tmp_x] = tmp[y][x] + 1;
			q.push(make_pair(tmp_y, tmp_x));
			if (lab[tmp_y][tmp_x] != 2) val = max(val, tmp[tmp_y][tmp_x]);
			
		}
	}

	while (!re_q.empty()) {
		lab[re_q.front().first][re_q.front().second] = 2;
		re_q.pop();
	}

	return val;
}

int checkInfection() {
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (tmp[i][j] == 0 || lab[i][j] == 2) cnt++;
		}
	}
	if (cnt > virus.size()) return 0;
	return 1;
}

void copyLab() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tmp[i][j] = lab[i][j];
		}
	}
}