(c++)백준 17142번: 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

[풀이]

dfs 조합으로 활성화시킬 바이러스 M개를 뽑고, 그에 따라 bfs를 이용하여 확산시켜야 하는 문제였다.

bfs level(깊이)갱신을 잘못 이해해서 애먹었다. 각 칸마다 점수가 있는게 아니므로 처음방문 했을 때 시간이 최단 시간임을 명심하자! 한 번 방문했으면 다시 방문하지 않아도 됨!!

빈칸을 미리 세어두고 바이러스를 확산시켰을 때 방문하는 빈칸들의 개수와 비교하여 같으면 최솟값을 갱신하였다.

각 경우마다 모든 빈 칸에 바이러스 퍼뜨리는 시간은 가장 마지막으로 방문되는 빈칸이 채워지는 시간이다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>//memset
#include <algorithm>//min
using namespace std;

struct Pos {
	int x, y;
};

int N, M;
int Map[50][50];
int spread[50][50];//화산되는 시간 저장에 사용
vector<Pos>v;//바이러스 위치 저장
bool Select[10];//활성시킬 바이러스 체크
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int Min = 987654321;
int emptyPlace = 0;
int virusCnt = 0;

void bfs() {
	memset(spread, -1, sizeof(spread));
	queue<Pos>q;
	//활성시킬 바이러스들 미리 큐에 넣어두기
	for (int i = 0; i < virusCnt; i++) {
		if (Select[i] == true) {
			q.push({ v[i].x,v[i].y });
			//0초부터 시작
			spread[v[i].x][v[i].y] = 0;
		}
	}
	int spreadPlace = 0;
	int totalTime = 0;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		//상하좌우 확산
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (Map[nx][ny] == 1)
				continue;
	
			/*if (Map[nx][ny] != 1 && spread[nx][ny] == -1) {
				spread[nx][ny] = spread[x][y] + 1;
				if (Map[nx][ny] == 0) {
					spreadPlace++;
					totalTime = spread[nx][ny];
				}
				q.push({ nx,ny });
			}*/
			//다음 칸이 비활성 바이러스면
			if (Map[nx][ny] == 2 && spread[nx][ny] == -1) {
				//활성으로 바꾸고 큐에 넣어주기
				spread[nx][ny] = spread[x][y] + 1;
				q.push({ nx,ny });
			}
			//다음 칸이 빈칸이면
			else if (Map[nx][ny] == 0 && spread[nx][ny] == -1) {
				spread[nx][ny] = spread[x][y] + 1;
				q.push({ nx,ny });
				spreadPlace++;
				//마지막엔 처음 활성 바이러스로부터 가장 멀리 떨어진 칸이 채워짐
				totalTime = spread[nx][ny];
			}
		}
	}
	//모두 퍼뜨렸으면
	if (spreadPlace == emptyPlace)
		Min = min(Min, totalTime);
}

void getActiveVirus(int idx, int cnt) {
	if (cnt == M) {
		//확산시키기
		bfs();
		return;
	}
	for (int i = idx; i < virusCnt; i++) {
		if (Select[i] == true)
			continue;
		Select[i] = true;
		getActiveVirus(i, cnt + 1);
		Select[i] = false;
	}
}

void solution() {
	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) {
				//비활성 바이러스 위치 저장
				v.push_back({ i,j });
				virusCnt++;
			}
			//빈칸 개수 미리 세어두기
			if (Map[i][j] == 0)
				emptyPlace++;
		}
	}
	getActiveVirus(0, 0);
	/*
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << spread[i][j] << ' ';
		}
		cout << '\n';
	}
	*/
	if (Min == 987654321)
		Min = -1;
	cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}