BOJ 17142 : 연구소 3

문제

---

문제 풀어보기

17142번: 연구소 3

 

풀이

---

 

 

간단하게 설명하면 모든 경우에 대해서

BFS를 전부 돌려봐야 하는 문제입니다.

 

 

 

어떤 바이러스를 활성화할 것인지를 고르는 방법이 포인트인데,

조합을 써도 되고 방법은 여러가지 입니다.

 

 

 

저는 비트 마스크를 사용해서 풀었으니 참고하시면 좋을 것 같습니다.

 

 

 

코드

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>


using namespace std;

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

int n, m;
int dist[55][55];
int ans = 0;
bool check2 = false;

// m개만 선택된 이진수를 색출
bool ok(long long a) {

	int k = 0;
	
	while (a > 0) {
		if (a & 1) {
			k++;
		}
		a = (a >> 1);

	}
	if (k == m) return true;
	return false;

}


int main() {

	cin >> n >> m;
	vector< vector<int>> arr(n, vector<int>(n));
	vector<pair<int, int>> virus;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 2) {
				virus.push_back({ i, j });
			}
		}
	}

	// 비트마스크 생성
	int sz = virus.size();
	vector<long long> choice;
	for (long long i = 0; i < (1 << sz); i++) {
		if (ok(i)) {
			choice.push_back(i);
		}

	}


	queue<pair<int, int>> q;
	// 모든 경우의 수 탐색
	for (long long bit : choice) {
		memset(dist, -1, sizeof(dist));
		for (int i = 0; i < sz; i++) {
			if (bit & (1 << i)) {
				dist[virus[i].first][virus[i].second] = 0;
				q.push({ virus[i].first, virus[i].second });
			}
		}
		int time = 0;
		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[nx][ny] == 1) continue;
				if (dist[nx][ny] != -1) continue;

				q.push({ nx,ny });
				dist[nx][ny] = dist[x][y] + 1;
                
				// 비활성 바이러스를 활성시키는 시간은 제외
				if (dist[nx][ny] > time && arr[nx][ny] != 2) time = dist[nx][ny];
			}

		}
		
        // 전부 감염시켰는지
		bool check = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] == -1 && arr[i][j] == 0) {
					check = false;
				}
			}
		}

		if (check) {
			check2 = true;
			if (ans == 0 || ans > time) ans = time;
		}
	}

	
	if (ans == 0) {
		if (check2) cout << 0 << '\n';
		else cout << -1 << '\n';

	}
	else cout << ans << endl;
	



	return 0;
}