[백준 17141] 연구소 3

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

17142번: 연구소 3

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
int N, M;
int choice[10 + 2];	// 최대 10개까지 선택 가능
int visited[50 + 2][50 + 2];
int board[50 + 2][50 + 2];
int v_size;	// 바이러스를 저장한 벡터의 사이즈
int min_val = 0x7fffffff;	// 최소 시간
int cnt_zero;	// 빈칸의 개수를 미리 세어놓음 

struct _st
{
	int x;
	int y;
	int t;
};

std::vector<_st> Virus;
std::queue<_st> Q;

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 2) Virus.push_back({ i, j, 0 });		// 0초부터 시작 
			if (board[i][j] == 0) cnt_zero++;
		}
	}
	v_size = Virus.size();
}



int BFS()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	// BFS 여러번 돌리므로 방문배열 초기화
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), -1);	// 0초부터 시작이므로 -1로 초기화해줌 
	// 큐 초기화
	Q = {};
	for (int i = 0; i < M; i++) {
		int vx = Virus[choice[i]].x;
		int vy = Virus[choice[i]].y;
		int vt = Virus[choice[i]].t;

		visited[vx][vy] = 0;
		Q.push({ vx, vy, vt });
	}

	int max = 0;
	int tmp_zero = 0;
	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;	// 영역 밖이라면 스루
			if (board[nx][ny] == 1) continue;		// 벽이라면 스루
			if (visited[nx][ny] > -1) continue;		// 이미 방문했다면 스루
			
			visited[nx][ny] = data.t + 1;
			Q.push({ nx, ny, data.t + 1 });
			if (board[nx][ny] == 0) {	// 빈칸을 채웠다면 max값 갱신, tmp_zero 값 증가		// 비활성 바이러스인 경우 max값 갱신 대상에서 제외 
				max = (max < visited[nx][ny]) ? visited[nx][ny] : max;
				tmp_zero++;
			}
		}
	}
	if (tmp_zero != cnt_zero) return 0x7fffffff;	// 빈칸을 다 채우지 못함 
	return max;
}



void Combi(int s, int n)
{
	if (n == M) {
		int tmp = BFS();
		min_val = (tmp < min_val) ? tmp : min_val;
		return;
	}
	for (int i = s; i < v_size; i++) {
		choice[n] = i;
		Combi(i + 1, n + 1);
	}
}


int main()
{
	input();
	Combi(0, 0);
	if (min_val == 0x7fffffff) printf("%d\n", -1);
	else printf("%d\n", min_val);
	return 0;
}

어휴~~~ 거지같아 ~~~~!

 

 

전반적인 구조는 기존의 연구소, 연구소 2 문제와 동일하다. 

DFS로 조합의 경우의 수 찾고 BFS 돌려서 바이러스를 퍼트리는 것이다.

다만, 중요한 포인트였던 두 가지는

1. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다

2. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다. 

 

 

// input( ) 함수

루프를 돌면서 해당 칸에 바이러스가 있다(2)면 Virus라는 벡터에 좌표를 저장한다. 해당 칸은 바이러스가 퍼지는데 0초의 시간이 걸리므로, t는 0으로 저장한다. 

한편 빈 칸(0)이라면 cnt_zero 변수를 증가시킨다. 해당 변수는 이후 BFS 함수를 돌리면서 모든 빈 칸에 바이러스를 퍼트렸는지 판단하는 용도로 사용해줄 것이다. 

 

 

// BFS( ) 함수

전형적인 BFS 함수의 구조와 동일하지만, 1번 주의사항을 잘 구현해야 한다.

비활성 바이러스는 활성 바이러스를 만나면 상태가 바뀌지만(비활성 -> 활성), 이것을 바이러스가 퍼트려졌다고 볼 수는 없다. 즉, 빈칸에 바이러스를 퍼트린 것은 아니다. 따라서 한 번의 BFS에서 바이러스가 퍼지는 시간을 구할 때, 비활성 바이러스가 활성화된 경우는 제외해야 한다. 이를 코드로 구현한 부분은 다음과 같다. 

if (board[nx][ny] == 0) {
	// 비활성 바이러스인 경우 max값 갱신 대상에서 제외 
	max = (max < visited[nx][ny]) ? visited[nx][ny] : max;
    // 빈칸을 채웠다면 max값 갱신, tmp_zero 값 증가
	tmp_zero++;
	}

마지막으로 while루프를 빠져나오면서 만약 tmp_zero가 맵을 입력받으면서 기록해 놓았던 빈칸의 개수(cnt_zero)와 같지 않으면 모든 빈칸을 채운것이 아니다. 따라서 이 때는 빈칸을 다 채우지 못했으므로 시간을 0x7fffffff 로 리턴한다. 그렇지 않다면 모든 빈칸을 채우는데 걸린 시간인 max를 리턴해준다. 

 

 

// Combi( ) 함수

입력받은 바이러스 개수 Virus.size()개에서 M개를 선택하고, 그렇게 선택한 M개를 대상으로 BFS를 돌린 결과들 중 가장 작은 값을 min_val에 저장한다.

모든 조합의 경우를 다 시도해봤지만 여전히 min_val이 0x7fffffff인 경우, 어떠한 경우에도 연구소에 바이러스를 퍼트릴 수 없기 때문에 -1을 출력한다. 그게 아니라면 min_val을 출력해주면 된다.