백준 17142 ( 연구소 3 )

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

해당 문제는 N과 K가 주어지며 N * N 개의 배열 안에서 바이러스를 퍼뜨려 맵 전체에 바이러스가 퍼질 수 있는 최단시간을 구하는 문제이다. 이때 조건은 바이러스는 무작위로 주어지며 해당 바이러스는 모두 활성화 되어있지 않으며 K개의 바이러스만 활성화 시켜 바이러스를 퍼트린다.

따라서 K개의 바이러스 조합을 만들어 어떤 바이러스 조합이 최소의 시간으로 맵 전체에 바이러스를 퍼트릴 수 있는지 구하면 된다.

풀이 :

1. DFS를 사용하여 어떤 위치의 바이러스를 활성화 시킬지 조합으로 구성한다.

2. 1에서 선택한 조합으로 Queue에 해당 조합의 바이러스를 Push 한 뒤 BFS를 사용하여 해당 조합의 바이러스가 전부 퍼졌을 때의 경우를 구한다.

+ 주의사항

BFS 를 사용하여 바이러스가 퍼지는 경우중 만약 바이러스가 퍼진 위치가 비활성화된 바이러스라면 시간만 +1 해주며 따로 Cnt 는 하지않는다. 왜냐하면 해당 위치의 바이러스를 1초 뒤 활성화 시키는 것이지 빈칸에 바이러스가 퍼지는 것이 아니기 때문이다. 추가로 바이러스가 퍼지는 위치가 빈 칸이라면 Cnt를 now.time +1 로 증가시켜 빈 칸으로 바이러스가 퍼졌을 때의 시간을 Cnt에 추가한다. 

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
struct Node{
	int y, x;
	int cnt, time;
};
int minn = 1000000;
int checkY[4] = { 0, 0, 1, -1 };
int checkX[4] = { 1, -1, 0, 0, };
int map[50][50];
int visit[50][50];
int cpMap[50][50];
int n, k, byLen;
vector<Node> byList;
vector<Node> result;

bool checkList(){
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (map[i][j] == 0 && visit[i][j] == 0) return false;
		}
	}
	return true;
}

int bfs(vector<Node> result){
	int resCnt = 0;

	memcpy(visit, cpMap, 4 * 50 * 50);
	queue<Node> qu;
	for (int i = 0; i < k; ++i){
		visit[result[i].y][result[i].x] = 1;
		qu.push(result[i]);
	}

	while (!qu.empty()){
		Node now = qu.front();

		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy < 0 || dx < 0 || dy >= n || dx >= n) continue;
			if (map[dy][dx] == 1 || visit[dy][dx] == 1) continue;
            // 빈칸일 경우 현재 시간에 +1 값을 카운트한다.
			if (map[dy][dx] == 0){
				qu.push({ dy, dx, now.time + 1, now.time + 1 });
			}
            // 비활성화 된 바이러스일 경우 시간만 변경한다.
			if (map[dy][dx] == 2){
				qu.push({ dy, dx, 0, now.time + 1 });
			}
			visit[dy][dx] = 1;
		}
		if (now.cnt > 0) resCnt = now.cnt;
		qu.pop();
	}
	if (checkList() == true) return resCnt;
	else return -1;
}

// 조합 선택
void dfs(int level, int idx){
	if (level == k){
		int tmp = bfs(result);
		if (tmp != -1){
			if (minn > tmp) minn = tmp;
		}
		return;
	}

	for (int i = idx; i < byLen; ++i){
		result.push_back(byList[i]);
		dfs(level + 1, i + 1);
		result.pop_back();
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> k;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> map[i][j];
			if (map[i][j] == 2) byList.push_back({ i, j, 0, 0 });
		}
	}

	byLen = byList.size();
	dfs(0, 0);
	if (minn == 1000000) minn = -1;
	printf("%d", minn);
}