[BOJ] 17142번 연구소 3

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

17142번: 연구소 3

이 문제는 작년 상반기 삼성전자 인턴때 풀었던 것으로 기억나는 데, 그 때 바이러스가 이미 있는 부분에 대해서 시간을 체크해서 그거 찾느라 시간이 오래 걸렸었다. 문제를 잘 읽었으면 그런 일은....

 

 

문제

바이러스 중 M개를 활성화 시켜서, 모든 빈칸에 바이러스를 퍼뜨리는 최단 시간을 구하는 것이다

 

 

 

풀이

이 문제는 BackTracking + BFS를 이용하고 약간의 조건들을 생각해 주어야 하는 전형적인 삼성 A형 문제이다.

 

1. 우선, 바이러스 중 M개를 선택한다. (BackTraking, 조합)
2. 그 다음, 모든 빈칸에 바이러스를 퍼뜨린다. (BFS) 주의해야 할 점은 바이러스를 퍼뜨릴 때, 이미 빈칸에 바이러스가 모두 퍼진 경우 퍼뜨리는 동작을 끝내야 한다. 계속 퍼뜨리면서 시간을 증가시켜 주면 안된다..

 

실수 했던 부분

• 같은 실수를 했다....
• 그리고 j를 i로 잘못써서 무한루프 도는 실수를 했다. 집중 안하면 생기는 실수..

//연구소의 바이러스 M개 활성상태로 변경
//활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변함
//모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하기
//만약 모든 빈칸에 바이러스를 못 퍼뜨리면 -1 출력
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
int N, M, answer, cnt;
int map[51][51];
bool visited[51][51];
pair<int, int> selected[10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<pair<int, int>> virus;

int bfs(int cnt) {
	//활성된 바이러스들 큐에 넣어준다.
	queue<pair<int, int>> q;
	for (int i = 0; i < M; i++) {
		q.push(selected[i]);
		visited[selected[i].first][selected[i].second] = true;
	}

	int t = -1;
	while (!q.empty()) {
		t++;
		
		//모든 빈칸에 바이러스를 퍼뜨린 경우
		if (cnt == 0) {
			break;
		}

		int sz = q.size();
		for (int i = 0; i < sz; i++) {
			int cy = q.front().first;
			int cx = q.front().second;
			q.pop();

			for (int j = 0; j < 4; j++) {
				int ny = cy + dy[j];
				int nx = cx + dx[j];
				if (ny <= 0 || nx <= 0 || ny > N || nx > N) continue;
				if (map[ny][nx] == 1) continue;
				if (visited[ny][nx]) continue;
				if (map[ny][nx] == 0) cnt--;
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}
		}	
	}
	
	if (cnt != 0) t = 2500;

	return t;

}
void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			visited[i][j] = false;
		}
	}
}
void dfs(int depth, int start) {
	//M개를 뽑은 경우
	if (depth == M) {
		init();
		answer = min(answer, bfs(cnt));
		return;
	}

	for (int i = start; i < virus.size(); i++) {
		selected[depth] = virus[i];
		dfs(depth + 1, i + 1);
	}
}
int main() {
	answer = 2500;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) cnt++;
			if (map[i][j] == 2) virus.push_back({ i,j });
		}
	}

	//빈칸이 없는 경우
	if (cnt == 0) {
		cout << 0;
		return 0;
	}

	//M개를 뽑는다.
	dfs(0, 0);

	if (answer == 2500) cout << -1;
	else cout << answer;

	return 0;
}