[BOJ 17142] 연구소 3 (C++)

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

17142번: 연구소 3

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 987654321

using namespace std;

int N, M;
int graph[51][51];
int ans = MAX;
vector<pair<int, int> > viruses;

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

void bfs(vector<bool>& temp) {
	int visited[51][51] = { 0, };
	queue<pair<int, int> > q;
	for (int i = 0; i < temp.size(); i++) {
		int x = viruses[i].first;
		int y = viruses[i].second;
		if (temp[i]) {
			visited[x][y] = 1;	//활성화 바이러스
			q.push({ x,y });
		}
		else {
			visited[x][y] = -1;		//비활성화 바이러스
		}
	}
	while (!q.empty()) {
		int vx = q.front().first;
		int vy = q.front().second;
		q.pop();
		if (ans!=MAX && visited[vx][vy] - 1 > ans)		//답 나온것보다 시간이 더 걸려서 퍼진 바이러스일 경우 탐색 중지
			break;
		for (int i = 0; i < 4; i++) {
			int nx = vx + dx[i];
			int ny = vy + dy[i];
			if (nx<=0 || ny<=0 || nx>N || ny>N)
				continue;
			if (visited[nx][ny] == 0 && graph[nx][ny] == 0) {
				visited[nx][ny] = visited[vx][vy] + 1;		//퍼뜨림
				q.push({ nx,ny });
			}
			if (visited[nx][ny] == -1 && graph[nx][ny] == 2) {		//비활성화 바이러스 만날경우
				visited[nx][ny] = visited[vx][vy] + 1;
				q.push({ nx,ny });
			}
		}
	}
	bool flag = false;
	int val = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (graph[i][j] == 0 && visited[i][j] == 0) {
				flag = true;		//virus 다 안퍼졌을때
				break;
			}
			if (graph[i][j] == 0) {		
				val = max(val, visited[i][j] - 1);
			}
		}
	}
	if (!flag) {
		ans = min(ans, val);
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> graph[i][j];
			if (graph[i][j]==2)
				viruses.push_back({ i,j });
		}
	}
	vector<bool> temp(viruses.size()-M, false);
	temp.insert(temp.end(), M, true);
	do {
		bfs(temp);
	} while (next_permutation(temp.begin(), temp.end()));
	if (ans == MAX)
		ans = -1;
	cout << ans << "\n";
	return 0;
}

 

활성화 바이러스를 놓는 모든 경우의 수를 탐색하여 최소값을 구한다.

한 case를 탐색할 때 bfs 탐색을 한다.

 

이 문제의 포인트는 활성화 바이러스에 인접한 비활성화 바이러스도 탐색 대상으로 큐에 넣어주는 것(비활성화 바이러스도 활성화 바이러스 만나면 활성화 되는 조건), 퍼지는 시간을 계산할 때 빈칸일때만 count 해주는 방식을 취하는 것이다.

 

탐색 종료 후 virus 퍼졌는지 체크하는 방식을 취해줬다. 

그러나 빈칸을 탐색할 때마다 그 수를 세어줘서 그것이 빈칸의 총 갯수와 일치할 때, 바이러스가 다 퍼진 것으로 간주하면 된다. 

 

나는 visited 배열, distance 배열을 따로 구분하지 않고 visited 배열 1개만 만들어서 했는데 이러면 코딩하기 불편하고 가독성도 떨어진다. 다른 분들의 코드(https://kimtaehyun98.tistory.com/101) 를 참조하니, visited를 아직 하지 않고 & 벽이 아닌 부분을 방문하고, 큐에 넣는다. 

또한 비활성 바이러스가 아닐 경우에만(즉 빈 칸일 때만), 걸릴 수 있는 시간을 갱신해주고 빈 칸일때를 체크해서 총 빈칸의 수와 같아질 때 바이러스가 퍼졌다고 간주하며, answer 값을 갱신하는 방식이다.

또한 next_permutation으로 조합을 구하는 대신, 백트래킹을 이용해 경우의 수를 구해도 된다.