백준 17142 연구소 3

 

1. 연구소에 비활성 바이러스 5개가 존재하고 3개를 활성시킬시 5개에서 3개를 뽑는 경우의 수를 다 구해야 한다.(dfs로 구현했다)

2. 3개를 선정후 각 사항에 맞게 몇시간후에 바이러스가 연구소를 차게 하는지 bfs를 통해 계산한다. - 여기서 유의 사항에 주목해야 하는데 중요한건 '비활성 바이러스'를 벽으로 보면 안된다는 거다. 즉 다 채우고 비활성바이러스가 나머지 항목에 있으면 끝내줘야 한다. 비활성바이러스쪽으로 들어가면서 시간을 더 투자해선 안된다. 해결방법은 처음에 감염시켜야 할 연구소방의 갯수를 기억하고 나중에 비교한다. (처음 한 방법은 한번 탐색할때마다 전체 염구소를 탐색해서 끝났는지 확인하는건데 이 경우는 너무 많은 시간을 소비하는 별로인 알고리즘이였다.)

3. 위치를 변경하고 계산해 가장 작은 시간을 출력한다.

 

 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct {
	int x;
	int y;
}pos_virus;

int N, M, max_result=numeric_limits::max(),K;
int map[50][50], c_map[50][50];
bool selected[10];
vector pv;
queue q;
int dir_x[4] = { 1,-1,0,0 }, dir_y[4] = { 0,0,-1,1 };
bool visit[50][50];

void Input() {
	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) pv.push_back({ j, i});
			if (map[i][j] == 0) K += 1;
		}
	}
}

void circle(int &infect, int &times) {
	int x = q.front().x;
	int y = q.front().y; q.pop();
	for (int i = 0; i < 4; i++) {
		int next_x = x + dir_x[i];
		int next_y = y + dir_y[i];
		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N || 
			map[next_y][next_x] == 1 || visit[next_y][next_x]) continue;
		visit[next_y][next_x] = true;
		if (c_map[next_y][next_x] == 0) {
			times = c_map[y][x]+1;
			infect += 1;
		}
		c_map[next_y][next_x] = c_map[y][x] + 1;
		q.push({ next_x, next_y });
	}
}

void copy_map() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			c_map[i][j] = map[i][j];
			visit[i][j] = false;
		}
	}
}

void dfs(int start, int depth) {
	if (depth == M) {
		copy_map();
		for (int i = 0; i < pv.size(); i++) {
			if (selected[i]) {
				q.push({ pv.at(i).x,pv.at(i).y  });
				c_map[pv.at(i).y][pv.at(i).x] = 0;
				visit[pv.at(i).y][pv.at(i).x] = true;
			}
			
		}
		int infect = 0, times=0;
		while (!q.empty()) {
			circle(infect,times);
		}
		if (infect == K && max_result > times) max_result = times;
		return;
	}

	for (int i = start; i < pv.size(); i++) {
		selected[i] = true;
		dfs(i + 1, depth + 1);
		selected[i] = false;
	}
}

void Solve() {
	Input();
	dfs(0,0);
}



int main(void) {
	Solve();
	printf("%d", max_result == numeric_limits::max() ? -1 : max_result);
	return 0;
}