17142 연구소 3

문제링크

코드 설명

연구소 1,2 문제와는 다르게 3은 비활성 바이러스가 활성바이러스로 변하게된다. 이를위해 활성바이러스로 변할시 큐에 다시 넣어주는 작업을 하였다.

그외에는 같은 방식으로 완전탐색으로 M만큼 바이러스를 정하고 BFS를 사용하여 카운트 하였다.
완전탐색의 경우 백업map을 잘 설정하자 !

바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다 -> 계속해서 벽에 막힐경우 생각하기(infect_room , empty_place 각각 카운트하여 생각)

코드

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int N, M;
int map[51][51];
vector<pair<int, int> > wall;
vector<pair<int, int> > virus;
vector<pair<int, int>> real_virus;
int time_map[51][51];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int empty_place;
int answer=9999;
bool flag;

void BFS() {
	//큐에 인덱스 등록
	int total_time = 0;
	int infect_room = 0;
	int cnt = 0;
	queue<pair<int, int>> q;
	for (int i = 0; i < real_virus.size(); i++) {
		q.push({ real_virus[i].first,real_virus[i].second });
		
	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 1) { //벽일경우
				time_map[y][x] = -2;
			}
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			// 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.(1초소요)
			if (time_map[ny][nx] == -1) {
				q.push({ ny,nx });
				time_map[ny][nx] = time_map[y][x] + 1;
				if (map[ny][nx]==0) {
					infect_room++;
					total_time = time_map[ny][nx];
				}
			}
		}
	}



	if(infect_room == empty_place) answer = min(answer, total_time);

	
}

void run(int level,int now) {
	if (level == M) {//바이러스 위치 M개 정하기
		for (int i = 0; i < real_virus.size(); i++) {
			time_map[real_virus[i].first][real_virus[i].second] = 0;
		}
		
		BFS();
		

		memset(time_map, -1, sizeof(time_map));
		return;
	}
	for (int i = now; i < virus.size(); i++) {
		real_virus.push_back({ virus[i].first,virus[i].second });

		run(level + 1, i + 1);
		real_virus.pop_back();
	}


}
int main() {

	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] == 0) {
				empty_place++;
			}
			if (map[y][x] == 1) {
				wall.push_back({ y,x });
				
			}
			if (map[y][x] == 2) {
				virus.push_back({ y,x });
			}

		}
	}
	memset(time_map, -1, sizeof(time_map));
	run(0, 0); //바이러스 M개 고르기
	if (answer==9999) cout << -1;
	else cout << answer;



	return 0;
}