[백준/C++] 17142 연구소3 (BFS)

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

 

 

💡 문제 설명

 

비활성 바이러스의 위치가 2로 표시되는데 연구실 바이러스 M개를 활성시킨다는 것은 2로 표시된 위치 중에서 M 개를 선택해서 바이러스를 뿌리겠다는 것이다. 그리고 전체 빈 공간을 바이러스(비활성,활성 포함)로 모두 채우는데 얼마나 걸리는 지를 계산 하는 문제이다. 

전형적인 bfs이지만 조합이 한 번 들어갔다는 점에 있어서 아주 살짝 까다로운 느낌을 내려고 한 문제이다.  

 

💡 문제 풀이

 

먼저 바이러스 정보들을 struct info에 저장하고 이 struct를 벡터로 구성하여 virus정보를 저장한다. 

 

조합을 통해서 바이러스의 활성 상태를 on/off 해 주면서 조합을 구한다. 

조합은 중복되지 않는 숫자들을 고르는 것이기 때문에 for (int i = inx ; i < virus.size() ; i ++ )

for 문에서 i가 inx부터 시작되는 것이 중요하다. 이 부분을 놓치면 조합이 아니라 순열을 고르게 되는 것이다. 

 

활성화된 바이러스의 개수가 M개를 충족하였으 때 bfs(solve)를 돌면서 전체 빈공간을 채우는데 걸리는 최소 시간을 구한다. 매번 solve를 실행 할 때마다 visit 초기화를 해 주고 활성화된 바이러스들을 큐에 넣어주고 시작해야 한다. 

 

#define _CRT_SECURE_NO_WARNINGS
#define ABS(A,B) A>B? A-B: B-A
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
int dx[4] = { 0,0,1,-1};
int dy[4] = {-1,1,0,0};
int map[55][55];
bool visit[55][55];
int N, M;
struct info { int y, x,time; bool active; };
std::vector<info> virus;
int time = 9876543210;
bool check = false;
int place;
void solve() {
	std::queue<info> V;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < virus.size(); i++) {
		if (virus[i].active) {
			V.push(virus[i]);
			visit[virus[i].y][virus[i].x] = true;
		}
	}
	int curVirus = 0;
	while (!V.empty()) {
		info head = V.front();
		V.pop();
		if (head.time > time) break;

		for (int i = 0; i < 4; i++) {
			int ny = head.y + dy[i];
			int nx = head.x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			if (visit[ny][nx] || map[ny][nx] == 1) continue;
			if (map[ny][nx] == 0) {
				visit[ny][nx] = true;
				V.push({ ny,nx,head.time + 1,true });
				curVirus++;
			}
			else if (map[ny][nx] == 2) {
				visit[ny][nx] = true;
				V.push({ ny,nx,head.time + 1,true });
			}
		}
		if (curVirus == place) {
			time = head.time+1 < time ? head.time+1 : time;
			check = true;
			break;
		}
	
	}
}
void comb(int inx, int cnt) {
	if (cnt == M) {
		solve();
		return;
	}
	for (int i = inx; i < virus.size(); i++) {
		if (virus[i].active) continue;
		virus[i].active = true;
		comb(i + 1, cnt + 1);
		virus[i].active = false;
	}
}
int main() {
	scanf("%d %d", &N, &M);
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%d", &map[y][x]);
			if (map[y][x] == 2) virus.push_back({ y,x,0,false });
			if (map[y][x] == 0) place++;
		}
	}
	if (place == 0) {
		printf("0");
		return 0;
	}
	comb(0, 0);
	if (!check) printf("-1");
	else printf("%d", time);
	return 0;
}