[백준] 17142번 : 연구소3 (C++) (삼성 SW 기출)

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

17142번: 연구소 3

브루트포스와 BFS 알고리즘을 사용하여 구현하였다.

 

맨 처음에 문제를 읽고 구현자체가 어려울 것 같진 않았지만, 테스트 케이스를 돌리다보니 예외처리와 효율성을 고려하는게 빡셌던 것 같다. 

(덕분에 디버깅만 거의 2시간 한것 같다ㅎㅎ)

 

애를 먹었던 부분은  "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 라는 조건이었다.

좀더 풀어서 설명해보자면, 비활성화된 바이러스가 있는 칸으로도 바이러스가 퍼질 순 있지만, 모든 빈칸에만 바이러스가 퍼지면 탐색을 마치고 시간 계산을 할 수 있다는 것이다. 

 

처음부터 이해한건 아니고, 계속 디버깅을 하다보니 이해하였다...위 조건을 구현하기 위해서 while문 안에서 매번 이중 for문을 통해 빈칸인데 바이러스가 안퍼진 부분이 있는지 체크해주었다. 

테스트케이스는 다 맞았고, 채점도 70%까지 잘 진행되다가................ 시간초과가 떠버렸다^^ 

 

따라서, 더 효율적인 방법을 생각해보았고 마침내 통과하였다!!

방법은,

1. 빈칸의 개수 blank변수를 선언하고, 입력받을때 blank++해주었다.

2. bfs시작시 blankcnt변수를 선언하여, 빈칸인 부분에 바이러스를 퍼뜨릴 때 blankcnt++를 해주었다.

3. while문 조건에 blankcnt < blank 을 추가해주었다.

4. blankcnt == blank인 경우만, 빈칸에 바이러스가 다 퍼졌다고 판단하여 최소시간을 계산하였다. 

 

 전체코드는 아래와 같다~!

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
int map[50][50]; //0:빈칸, 1:벽, 2: 바이러스
int visit[50][50];
int minTime = 987654321;//바이러스 모두 퍼지는 최소시간
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<pair<int,int>> v; //바이러스 위치
vector<pair<int, int>> tmp; //활성화 바이러스 위치
int tmpvisit[10]; //백트래킹
int blank; //빈칸 수 <- 시간초과때문에 사용


void SpreadVirus() { //활성화 바이러스 퍼뜨리기
	memset(visit, 0, sizeof(visit));
	queue<pair<int, int>> q;
	for (int i = 0; i < tmp.size(); i++){ //활성화 바이러스
		q.push(tmp[i]);
		visit[tmp[i].first][tmp[i].second] = 1;
	}
	int cnt = 0; //현재 시간
	int blankcnt = 0; //바이러스가 퍼진 빈칸의 수 <- 시간초과 방지

	while (!q.empty() && blankcnt<blank) { //bfs
		int size = q.size();
		cnt++; 
		while(size--){		
			int x = q.front().first;
			int y = q.front().second;
			q.pop(); 		
			for (int i = 0; i < 4; i++){
				int cx = x + dx[i];
				int cy = y + dy[i];
				if (cx >= 0 && cx < N && cy >= 0 && cy < N && !visit[cx][cy] && map[cx][cy] != 1) {//범위o,방문x,벽x
					if(map[cx][cy]==0) blankcnt++; //빈칸인데 바이러스 퍼진경우 <- 비활성화 바이러스 칸이랑 차별위해
					visit[cx][cy] = 1;
					q.push({ cx,cy });
				}
			}
		}
	}
	if (blankcnt == blank) minTime = min(minTime, cnt);
}

void Activate(int cur) { //활성화 바이러스 M개 선택 : 백트래킹
	if (tmp.size() == M) {
		SpreadVirus();
		return;
	}
	if (cur >= v.size()) return;
	for (int i = cur; i < v.size(); i++){
		if (!tmpvisit[i]) {
			tmpvisit[i] = 1;
			tmp.push_back(v[i]);
			Activate(i + 1);
			tmp.pop_back();
			tmpvisit[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	bool noVirus = true; //바이러스 유무
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) v.push_back({ i,j }); //바이러스
			if (map[i][j] == 0) { //빈칸
				blank++;
				noVirus = false;
			}
		}
	}
	if (!noVirus) Activate(0); //바이러스 있으면
	else minTime = 0; //바이러스 없으면
	cout << (minTime==987654321? -1 : minTime) << endl;
}