[백준 17142번 연구소 3] - C++

[백준 17142번 연구소 3]
https://www.acmicpc.net/problem/17142

[연구소 1]
https://velog.io/@statco19/boj-14502

기존의 연구소 문제와 거의 비슷하지만 시간제한이 빡빡해진 문제였다. 이전에는 6중 for문으로 벽을 골랐지만, 이번에는 DFS를 통해 조합을 구현하여 활성화 시킬 바이러스를 선택하였다.

풀이

1.

DFS를 사용하여 연구소에 존재하는 비활성화 바이러스 중 초기에 활성화시킬 바이러스를 3개 선택한다(next_permutation이라는 메서드를 사용할 수도 있다).

2.

3개의 바이러스를 기점으로 BFS를 통해 바이러스를 전파시킨다. 문제에서 연구소의 빈 칸이 존재하지 않게 하는 최단 시간을 구하라고 했기에 여기서 BFS라는 힌트를 얻을 수 있었다.

3.

BFS를 진행하면서 주의 해야 할 부분은 활성화된 바이러스 퍼져나가면서 비활성화 바이러스를 만나면 비활성화 바이러스가 활성화된다는 점과 비활성화 바이러스가 존재해도 빈 칸만 없으면 전파가 완료되는 조건을 충족한다는 점이다. 비활성화 바이러스가 활성화될 때도 시간은 물론 계속 흐른다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 987654321;
int n,m;
int totalSpace;
int map[51][51];
int vMap[51][51];
vector<pair<int,int> > virus;
vector<pair<int,int> > chosen;
int visited[10];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};

void spreadBfs(){
	int sec = 0;
	int space = totalSpace;
	int size = chosen.size();

	queue<pair<int,int> > q;
	memset(vMap,0,sizeof(vMap));
	for(int i=0;i<size;++i) {
		pair<int,int> p = chosen[i];
		q.push(p);
	}
	
	while(!q.empty() && space > 0) {
		int s = q.size();

		for(int i=0;i<s;++i) {
			pair<int,int> p = q.front();
			q.pop();

			int r,c;
			r = p.first; c = p.second;
			if(vMap[r][c] != 1) {
				vMap[r][c] = 1;
			}
			
			int nr,nc;
			for(int d=0;d<4;++d) {
				nr = r+dr[d];
				nc = c+dc[d];

				if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n)) {  // out of bound
					continue;
				}

				if(vMap[nr][nc]==1) {  // has visited
					continue;
				}

				// not visited yet
				if(map[nr][nc]==1) {  // wall
					continue;
				} else if(map[nr][nc] == 0 || map[nr][nc] == 2){  // map[nr][nc] == 0 or 2
					vMap[nr][nc] = 1;
					if(map[nr][nc] == 0) {
						space--;
					}
					q.push(make_pair(nr,nc));
				}
			}
		}
		sec++;
	}

	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(map[i][j] == 0 && vMap[i][j] == 0) {
				return;
			}
		}
	}

	ans = min(ans,sec);

	return;
}

void chooseDfs(int st, int depth) {
	if(depth == m) {
		spreadBfs();
		return;
	}

	int vCnt = virus.size();
	for(int i=0;i<vCnt;++i) {
		if(!visited[i] && i>=st) {
			visited[i] = 1;
			pair<int,int> p = virus[i];
			chosen.push_back(p);
			chooseDfs(i+1, depth+1);

			chosen.pop_back();
			visited[i] = 0;
		}
	}

	return;
}


void sol() {

	// choose three virus coordinates
	chooseDfs(0,0);

	// after bfs, if the map is not fully contaminated, then break the loop
	// else if the map is full, make ans have the smaller time

	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d", &map[i][j]);
			if(map[i][j] == 2) {
				virus.push_back(make_pair(i,j));
			} else if(map[i][j] == 0) {
				totalSpace++;
			}
		}
	}

	sol();

	// if ans == 987654321, then ans = -1
	if(ans == 987654321) {
		ans = -1;
	}

	printf("%d\n", ans);
	
	return 0;
}

실행 결과