[백준 17142] 연구소 3

문제
바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제된다.
연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소의 크기는 NxN이며 빈 칸, 벽, 바이러스로 이루어져 있다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 활성화된다.
(0은 빈 칸, 1은 벽, 2는 바이러스)
M개의 바이러스를 선택하여 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구한다.

입력
첫째 줄에 N(4이상 50이하)과 바이러스 개수 M(1이상 10이하)를 입력한다.
이어서 NxN의 연구소 맵을 입력한다.

출력
모든 빈 칸이 바이러스가 되는 최소시간을 구하고 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다.

---

접근

3가지를 구현한데 집중을 하였다. 먼저 활성화 시킬 M개의 바이러스를 선택, M개의 바이러스를 활성화 시켜 퍼뜨리기, 모든 칸이 바이러스로 전염되었을 때 걸린시간 구하기

M개의 바이러스를 선택하기위해 연구소의 정보를 입력받을 때 바이러스의 위치를 따로 저장해두고 이를 DFS로 M개 선택하여 퍼뜨리는 함수에 넘긴다.

바이러스를 퍼뜨릴 때는 BFS를 활용한다.

또한 모든 칸이 바이러스로 전염되었을 때 시간을 구해야하기 때문에 초기에 빈 칸이 몇 개인지 카운트하여 저장해둔다.

그리고 바이러스를 퍼뜨리면서 빈 칸에 전염시켰을 경우 빈칸을 카운트하여 초기의 총 빈 칸과 맞는지 검사한다.

 

구현

초기에 입력받을 때 -2를 해주었는데 나중에 사용되지 않아 불필요하다. 오히려 가독성이 떨어졌다.

입력받은 위치가 바이러스면 virus라는 vector에 넣어주고 빈 칸을 카운트하여 total_empty에 저장한다.

	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
				virus.push_back({ i, j });
			else if (map[i][j] == 0)
				total_empty += 1;
			map[i][j] -= 2;
		}
	}

 

DFS를 통해 M개의 바이러스를 고른다.

M개의 바이러스를 선택 후에 BFS에 활성화시킬 바이러스의 위치를 넘겨준다.

그리고 모든 칸에 바이러스를 전염시켰을 경우 걸린시간을 받아 최솟값 비교를 한다.

void dfs(vector<pair<int, int>> picked, int next) {
	if (picked.size() == M) {
		answer = min(answer, bfs(picked));
		return;
	}
	for (int i = next; i < virus.size(); i++) {
		picked.push_back(virus[i]);
		dfs(picked, i + 1);
		picked.pop_back();
	}
}

 

바이러스를 퍼뜨리는 BFS에서 spread_map으로 방문표시 및 걸린시간을 기록한다. 

그리고 전달받은 바이러스의 위치를 큐에 넣고 spread_map에 0으로 활성화를 표시한다.

int bfs(vector<pair<int, int>> picked_virus) {
	int spread_map[50][50];
	queue<pair<int, int>> q;
	memset(spread_map, -1, sizeof(spread_map));
	for (int i = 0; i < picked_virus.size(); i++) {
		int y = picked_virus[i].first;
		int x = picked_virus[i].second;
		q.push({ y, x });
		spread_map[y][x] = 0;
	}

 

BFS로 바이러스를 퍼뜨리다가 빈 칸이 나오면 empty_cnt를 감소시켜 0이 되었을 때 모든 칸에 바이러스를 퍼뜨렸다고 판단하도록 한다.

이때 spread_map에서 최댓값을 반환한다. 만약 여기서 반환되지 않았다면 초기에 설정한 최댓값을 반환한다.

	int empty_cnt = total_empty;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (check_range(ny, nx) && map[ny][nx] != -1 && spread_map[ny][nx] == -1) {
				spread_map[ny][nx] = spread_map[cy][cx] + 1;
				q.push({ ny,nx });
				if (map[ny][nx] == -2)
					empty_cnt--;
			}
			if (empty_cnt == 0) {
				int sec = 0;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sec = max(sec, spread_map[i][j]);
					}
				}
				return sec;
			}
		}
	}
	return 987654321;

---

전체 코드

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;

int N, M;
int map[50][50];
int answer = 987654321;
int total_empty = 0;
vector<pair<int, int>> virus;
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool check_range(int y, int x) {
	return (y >= 0 && y < N) && (x >= 0 && x < N);
}


int bfs(vector<pair<int, int>> picked_virus) {
	int spread_map[50][50];
	queue<pair<int, int>> q;
	memset(spread_map, -1, sizeof(spread_map));
	for (int i = 0; i < picked_virus.size(); i++) {
		int y = picked_virus[i].first;
		int x = picked_virus[i].second;
		q.push({ y, x });
		spread_map[y][x] = 0;
	}

	int empty_cnt = total_empty;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (check_range(ny, nx) && map[ny][nx] != -1 && spread_map[ny][nx] == -1) {
				spread_map[ny][nx] = spread_map[cy][cx] + 1;
				q.push({ ny,nx });
				if (map[ny][nx] == -2)
					empty_cnt--;
			}
			if (empty_cnt == 0) {
				int sec = 0;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sec = max(sec, spread_map[i][j]);
					}
				}
				return sec;
			}
		}
	}
	return 987654321;
}
void dfs(vector<pair<int, int>> picked, int next) {
	if (picked.size() == M) {
		answer = min(answer, bfs(picked));
		return;
	}
	for (int i = next; i < virus.size(); i++) {
		picked.push_back(virus[i]);
		dfs(picked, i + 1);
		picked.pop_back();
	}
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
				virus.push_back({ i, j });
			else if (map[i][j] == 0)
				total_empty += 1;
			map[i][j] -= 2;
		}
	}

	vector<pair<int, int>> picked;
	dfs(picked, 0);
	if (answer == 987654321)
		answer = -1;
	cout << answer << endl;
	
}

/*

*/