C++ 17142번 연구소 3 (백준)

 

#include <bits/stdc++.h>
#define Q q.front()
using namespace std;

int n, m, ans = 1e9, blank = 0;
int Map[50][50] = {};
vector<pair<int, int> > virus;
vector<pair<int, int> > vec;
int V[4] = {-1, 0, 1, 0}, H[4] = {0, 1, 0, -1};

void BFS() {
	queue<tuple<int, int, int> > q; //큐
	int tmp = 0, cnt = 0; //tmp는 탐색 level, cnt는 0을 채운 개수
	bool v[n][n]; //방문 확인
	memset(v, false, sizeof(bool)*n*n); //초기화
	
	for(pair<int, int> i : vec) { //활성화 할 바이러스들을 큐에 삽입 및, 방문 처리
		int x = i.first;
		int y = i.second;
		v[x][y] = true;
		q.push(make_tuple(x, y, 0));
	}

	while(!q.empty()) { //BFS
		int x = get<0>(Q);
		int y = get<1>(Q);
		int z = get<2>(Q);
		q.pop();
		
		if(tmp < z) tmp = z; //방문 수준이 더 크다면 tmp을 더 큰걸로
		
		for(int i=0; i<4; i++) {
			x += V[i];
			y += H[i];
			if(x>=0 && y >= 0 && x < n && y < n && !v[x][y] && Map[x][y] != 1) { //벽이 아닌 경우 나아갈 수 있다. (방문 안했을 때)
				if(Map[x][y] == 0) ++cnt;
				if(cnt == blank) { //완전 탐색이 끝나지 않았지만 더이상 채울 공간이 없는 경우
					tmp = z+1;
					break;
				}
				v[x][y] = true;
				if(z < ans) q.push(make_tuple(x, y, z+1));
			}
			x -= V[i];
			y -= H[i];
		} if(cnt == blank) break;
	}

	if(cnt == blank && ans > tmp) ans = tmp;
	return;
}

void loop(int a, int k) { //활성화 할 바이러스 브루트포스
	if(k == m) {
		BFS();
		return;
	}
	
	int size = virus.size();
	for(int i=a+1; i<size; i++) {
		int x = virus[i].first;
		int y = virus[i].second;
		vec.push_back({x, y});
		loop(i, k+1);
		vec.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	blank = n*n; //모든 공간이 0이라고 가정
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			int tmp;
			cin >> tmp;
			Map[i][j] = tmp;
			if(tmp == 2) {
                --blank; //0이 아니다
                virus.push_back({i, j}); //바이러스의 위치는 따로 벡터에 넣음
            }
			else if(tmp == 1) --blank; //0이 아니다.
		}
		
	}
	
	if(blank > 0) loop(-1, 0);
	else ans = 0; //시작부터 0이 없는 경우
	
	if(ans == 1e9) ans = -1; 
	cout << ans;
}

 

풀이 : 브루트포스, BFS

 

1. 입력을 받되, 0을 입력받은 개수를 구하고, 바이러스의 경우 이것들의 위치를 따로 벡터에 저장합니다.

-만약 0이 없다면 바로 0을 출력하고 프로그램을 종료합니다.

 

2. m개의 활성화 시킬 바이러스들을 브루트포스로 구하며, 구할 때 마다 BFS을 돌립니다.

 

3. 2에서 활성화 시킬 바이러스들을 방문처리 및 Queue에 집어 넣은 다음 BFS을 시작합니다. 벽(1) 이 아니라면 방문하지 않은 경우 방문할 수 있으며, BFS 과정에서 더이상 0이 남아 있지 않다면 이 때 바로 BFS을 종료합니다.

 

4. BFS 종료 후, 만약 빈 공간을 다 채웠다면, BFS의 최대 수준(level)과 이전에 돌렸던 BFS들의 최대 수준(level)을 비교하고 더 작은값을 취합니다. 이것을 답으로 출력하게 됩니다.

 

5. 만약 0을 다 채우지 못했다면 -1을 출력합니다.

 

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

17142번: 연구소 3