[백준] 17141 연구소 2

[문제이해]

1. NxN 크기의 연구소가 있다. 연구소는 빈칸(0), 벽(1), 바이러스가 위치할 수 있는 후보 공간(2)으로 표현된다.

2. 승원이는 연구소의 특정 위치에 바이러스를 M개 놓을 것이다.

3. M개가 놓여진후 바이러스는 상,하, 좌, 우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초의 시간이 걸린다.

4. 연구소의 상태와 M이 주어졌을 때 모든 연구소 빈 칸에 바이러스가 퍼지는 최소 시간을 구해라

5. 첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

6. 둘째 줄에 연구소의 상태가 주어진다. 

 

[설계]

1. 연구소에는 바이러스가 위치할 수 있는 후보 공간들이 존재한다.

2. 이 후보 공간들에서 M개를 뽑아서 바이러스를 위치 시킨다. (후보 공간에서 M개를 뽑는 조합)

3. M개의 바이러스를 위치시키면 BFS를 통해 상하좌우로 바이러스를 퍼뜨린다.

4. 이때, 시간을 측정해야함으로 BFS 방문체크 배열에 시간을 기록해준다.

5. BFS를 통해 바이러스 퍼뜨리기 작업이 끝났으면, 바이러스가 모두 퍼졌는지 체크하고, 모두 퍼졌다면, 최소 시간을 갱신한다. 

 

[소스]

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;

typedef struct {
	int x, y;
}pos;

int n, m;
int map[50][50];
int visited[50][50];
int res = 1e9;

vector<pos> vir_loc;
vector<pos> v;
queue<pos> q;

int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };

void bfs() {

	while (!q.empty()){
		int x = q.front().x, y = q.front().y;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
			if (map[nx][ny] == 1) continue;
			if (visited[nx][ny]) continue;

			visited[nx][ny] = visited[x][y]+1;
			q.push({ nx,ny });
		}
	}

	int time=-1;

	for (int i = 0; i < n; i++) { //바이러스가 연구소에 모두 퍼졌는지 확인한다.
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) continue;
			if (visited[i][j] == 0) return; //모두 퍼지지 않았으면, 종료
			time = max(time, visited[i][j]);
		}
	}

	res = min(time-1,res); //최소 시간을 갱신해준다.
}


void dfs(int cnt) { // vir_loc(바이러스 공간 후보군)에서 m개만큼 뽑는다.
	if (v.size() == m) {
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < m; i++) { //m개를 뽑았으면, 바이러스를 위치시킨다.
			visited[v[i].x][v[i].y] = 1;
			q.push(v[i]);
		}

		bfs(); //바이러스를 퍼뜨린다.
		return;
	}

	for (int i = cnt; i < vir_loc.size(); i++) {
		v.push_back(vir_loc[i]);
		dfs(i + 1);
		v.pop_back();
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				vir_loc.push_back({ i,j }); //vir_loc 벡터에 바이러스 공간 후보군을 넣는다.
				map[i][j] == 0;
			}
		}
	}

	dfs(0);

	if (res == 1e9)
		cout << -1;
	else
		cout << res;
	return 0;
}