[17142] 연구소 3

풀이

연구소 1번과 비슷하게 풀 수 있고 주의할 점은 다음과 같습니다.

1. mm일 떄 걸리는 시간의 최대는 대략 2m이 아닌 m*m이라고 생각해야 한다. 바이러스가 ㄹ모양으로 퍼질 때를 고려해야 한다.
2. 문제를 잘 읽자 : 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAX 50
using namespace std;
int map[MAX][MAX];
int map2[MAX][MAX];
int n = 0, m = 0;
bool check[MAX][MAX];
vector<pair<int, int> > v;
vector<int> loop;
queue<pair<int, int> > q;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans = 50000;
void bfs(void) {
	int nx = 0, ny = 0;
	int t = 3;
	while (!q.empty()) {
		int qs = q.size();
		for (int i = 0; i < qs; i++) {
			pair<int, int> curr = q.front(); q.pop();
			for (int k = 0; k < 4; k++) {
				nx = curr.first + dx[k];
				ny = curr.second + dy[k];
				if (nx < 0 || nx >= n) continue;
				if (ny < 0 || ny >= n) continue;
				if (map2[nx][ny] == 0 && check[nx][ny] == false) {
					map2[nx][ny] = t;
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
				}
				else if (map2[nx][ny] == 2 && check[nx][ny] == false) {
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
				}
			}
		}
		t++;
	}
}

void printMap(void) {
	printf("----------------\n");
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", map2[i][j]);
		}
		printf("\n");
	}
	printf("----------------\n");
}

int main(void) {
	scanf("%d", &n);
	scanf("%d", &m);
	int zero = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				v.push_back(make_pair(i, j));
				loop.push_back(0);
			}
		}
	}
	//최대 m개까지 활성화 시키기
	for (int i = 0; i < m && i < loop.size(); i++) {
		loop[i] = 1;
	}

	//한 번이라도 전체에 퍼질 수 있으면 True
	do {
		//맵 복사
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map2[i][j] = map[i][j];
			}
		}
		//방문 초기화
		for (int i = 0; i < MAX; i++) {
			memset(check[i], false, sizeof(check[i]));
		}
		//3개 바이러스 선택
		for (int i = 0; i < loop.size(); i++) {
			if (loop[i] == 1) {
				q.push(v[i]);
				check[v[i].first][v[i].second] = true;
			}
		}
		//바이러스 확산
		bfs();
		//printMap();
		//바이러스 체크
		bool disperse = true; //모든 빈칸에 바이러스를 퍼뜨릴 수 있으면 true
		int curr_ans = 0; //현재 가장 오래걸린 칸
		for (int i = 0; i < n && disperse; i++) {
			for (int j = 0; j < n && disperse; j++) {
				if (map2[i][j] == 0) {
					disperse = false;
					break;
				}
				curr_ans = max(curr_ans, map2[i][j]);
			}
		}
		//전부 퍼뜨릴 수 있으면
		if (disperse && curr_ans >= 2) {
			ans = min(ans, curr_ans - 2);
			//printf("ans 갱신 %d\n", ans);
		}
	} while (prev_permutation(loop.begin(), loop.end()));

	//한 번도 전체에 퍼뜨릴 수 없으면
	if (ans == 50000) {
		printf("-1\n");
	}
	else {//한 번이라도  전부 퍼뜨릴 수 있으면
		printf("%d\n", ans);
	}
	return 0;
}