[삼성코테기출문제] 연구소 3

연구소 3

문제

이전에 풀었던 연구소의 업그래이드 버전이다.
연구소 문제는 벽을 3개를 세우고 바이러스를 확산 시키는 문제였다면, 연구소 3 문제는 맵의 정보를 주고 주어지는 바이러스들 중 M개의 바이러스를 활성화 시켜준다는 차이가 있다.

문제 풀이

입출력 조건

중요한 조건이 하나 있다. 모든 칸에 바이러스를 퍼트릴 수 있을 때 최소 시간을 구하는 문제이다. 자칫하면 그 부분을 생각하지 않고 큐가 공백 큐가 될 때까지 돌리고 그때의 시간을 구해서 틀릴수있는 문제이다.

풀이 과정

1. N, M을 입력받고 맵 정보를 입력 받을때 모든 바이러스 좌표를 false표시하여 저장한다. 그리고 빈 칸의 개수(k)를 세어준다. 이 k는 바이러스가 모든 빈 칸에 확산되었는지 확인하기 위함이다.
2. 저장된 바이러스 중 M개를 선택하는 ActVirus(int idx, int cnt)부분에서 dfs를 이용하여 활성화 시켜주고 해당 칸에 바이러스가 활성화 된 상태인지 비활성화 된 상태인지를 확인하기 위한 Step[N][N]을 -1로 초기화 시켜준다.
3. 활성화 된 바이러스를 큐에 넣고 그 바이러스가 존재하는 좌표를 0으로 마킹해주고 바이러스 확산 시키는 과정으로 넘어간다.
4. 바이러스를 탐색하기 위한 time변수와 확산된 빈 칸의 개수를 세기 위한 a를 선언해주고, 이 때 bfs를 이용하여 인접한 방향을 탐색하면서 if (Map[ny][nx] != 1 && Step[ny][nx] == -1) 벽이 아니면서 빈 칸인 부분이라면 현재 Step에서 1을 증가시켜준다.(활성화된 바이러스 부분은 0으로 바꿔주었으므로 이 부분이 시간을 의미한다)
5. 비활성화인 바이러스 좌표를 방문했을때는 바이러스를 활성화만 시켜주고 빈 칸이 아니므로 a값을 증가시키지 않는다. 만약 다음 칸이 빈 칸이면 a값을 증가시키고 다음까지의 Step을 시간에 넣어준다. 그리고 다음 좌표를 큐에 넣어준다.
6. 공백 큐가 되면 모든 칸을 돌았는지 확인하기 위해서 a와 k가 같은 경우에 최소시간인지 확인한다.
7. 이 과정을 반복하여 최소시간을 찾고 만약 최소시간을 찾지 못하여 1<<30으로 초기화 시켜줬던 Answer값이 변하지 않았다면 모든 칸에 대해 바이러스 확산 시키지 못했으므로 정답으로 -1을 출력하고 그렇지 않은 경우에는 Answer을 출력한다.

#include<iostream>
#include<queue>
using namespace std;
const int MAX = 50;
int N, M, k, Answer = 1 << 30;
int Map[MAX][MAX];
int Step[MAX][MAX];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,-1,0,1 };
//좌표, 활성상태
vector<pair<pair<int, int>, bool>> virus;
//좌표(x,y)
queue<pair<int, int>> Q;
void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 2) virus.push_back({ {j, i}, false });
			if (Map[i][j] == 0)k += 1;
		}
	}
}
void Process() {
	int time = 0, a = 0;
	while (!Q.empty()) {
		int curx = Q.front().first;
		int cury = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curx + dx[i];
			int ny = cury + dy[i];
			if (ny >= 0 && nx >= 0 && ny < N&&nx < N) {
				if (Map[ny][nx] != 1 && Step[ny][nx] == -1) {
					Step[ny][nx] = Step[cury][curx] + 1;
					if (Map[ny][nx] == 0) {
						a += 1;
						time = Step[ny][nx];
					}
					Q.push({ nx,ny });
				}
			}
		}
	}
	if (a == k && Answer > time)Answer = time;
}
void ActVirus(int idx, int cnt) {
	if (cnt == M) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Step[i][j] = -1;
			}
		}
		for (int i = 0; i < virus.size(); i++) {
			if (virus[i].second) {
				Q.push({ virus[i].first.first, virus[i].first.second });
				Step[virus[i].first.second][virus[i].first.first] = 0;
			}
		}
		Process();
		return;
	}
	for (int i = idx; i < virus.size(); i++) {
		if (!virus[i].second) {
			virus[i].second = true;
			ActVirus(i+1, cnt + 1);
			virus[i].second = false;
		}
	}
}
void Solution() {
	Input();
	ActVirus(0, 0);
	if (Answer == 1 << 30)cout << "-1" << "\n";
	else cout << Answer << "\n";
}
int main() {
	freopen("25.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}