BOJ 17142 연구소 3

#BOJ 17142 연구소 3

17142번: 연구소 3

#풀이

 

저번에 풀었던 연구소 문제와 많이 비슷하다.

 

일단 문제가 조금 애매 하게 나와있어서 왜 틀렸는지 몰랐다.

 

먼저 활성화된 바이러스가 번식을 하는데 비활성화된 바이러스를 만나면 활성화를 시킨다.

 

이렇게 바이러스가 벽이 아닌 모든 칸에 바이러스가 있을 때 까지 걸리는 최소 시간을 구하는 문제이다.

 

바이러스 중에서 m개를 골라서 활성화 시켜야 하기 때문에 그냥 간단하게 백트래킹을 사용해야 한다고 생각이 들었다. 그래서 조합으로 풀면 쉽게 풀릴 것 같아 next_permutation을 사용했다.

 

활성화된 바이러스를 번식시켜서 bfs를 사용하여 모든 곳에 방문을 했을 때 시간을 구하면 된다.

 

이 때 주의해야 할 것이 비활성화된 바이러스다.

 

비활성화 바이러스가 벽에 붙어 있다면 굳이 방문할 필요가 없다.

 

하지만 벽이 아닌 중앙에 있다면 활성을 시켜서 조금 더 빠르게 모든 칸을 방문해야 한다.

 

그래서 나는 그냥 벽일 때만 큐에 넣지 않고 가장 큰 시간을 구하기 전에 바이러스를 모두 -1 로 대입하고 했다.

 

#코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int arr[51][51];

int n, m;
vector<pair<int, int>> b_p;
int p[251];
int min_ans = 0x7f7f7f7f;
void solved() {
	do {
		queue<pair<int, int>> q;
		int vis[51][51] = { 0, };
		
		for (int i = 1; i <= b_p.size(); i++) {
			if (p[i] == 1) {
				q.push({b_p[i-1]});
				vis[b_p[i - 1].first][b_p[i - 1].second] = -1;
			}
		}

		while (!q.empty()) { // bfs
			auto cur = q.front(); q.pop();
			
			for (int i = 0; i < 4; i++) {
				int x = dx[i] + cur.first;
				int y = dy[i] + cur.second;

				if (x < 1 || y < 1 || x >n || y>n || arr[x][y] == 1 || vis[x][y] != 0) continue; // 비활성화된 바이러스는 활성화됨

				if (vis[cur.first][cur.second] == -1) // 활성화된 바이러스일 경우
					vis[x][y] = 1;
				else
					vis[x][y] = vis[cur.first][cur.second] + 1;
				q.push({ x,y });
			}

		}
		int max_time = 0;
		bool flag = 0;

		for (int i = 0; i < b_p.size(); i++) { // 모든 바이러스는 -1 최소 시간을 구하는데 사용하지 않음
			vis[b_p[i].first][b_p[i].second] = -1;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (vis[i][j] == 0 && arr[i][j] != 1) { // 빈칸인데 방문을 안했을 때 
					flag = 1;
					break;
				}
				
				if (max_time < vis[i][j]) { 
					max_time = vis[i][j];
				}
			}
			if (flag) { // 모든 빈칸이 바이러스가 아닐 때
				break;
			}
		}

		if ( flag == 0 && min_ans > max_time) {
			min_ans = max_time;
		}
		
	} while (next_permutation(p+1, p+1+b_p.size())); // 바이러스중에서 m개 선택 (조합)

}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 2)
				b_p.push_back({ i,j });
		}
	}
	for (int i = 0; i < m; i++) {
		p[b_p.size() - i] = 1;
	}
	solved();

	if (min_ans == 0x7f7f7f7f)
		min_ans = -1;

	cout << min_ans << '\n';
	return 0;
}