[백준 17142] 연구소 3

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

17142번: 연구소 3

 

요구사항

바이러스가 전부다 퍼질때까지의 최소시간 구하기

 

풀이

1. 바이러스 고르기

2. bfs로 바이러스 퍼뜨리기

3. 정답 출력

바이러스가 있는 칸을 전진할때는 시간은 증가하되, 정답으로는 간주안한다.

바이러스가 시작부터 차있을때도 처리해주어야 한다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct go {
	int x;
	int y;
	int cnt;
};
int map[51][51];
go virus[11];
int visit[51][51];
int Vvisit[11];
go wall[51 * 51];
int n, k;
int Vnum = 0;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 987654321;
int Vcnt = 0;
int wallcnt = 0;
void show() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << visit[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void dfs(int now, int cnt)
{
	if (now == Vnum) {
		if (cnt == k) {
			memset(visit, 0, sizeof(visit));
			queue<go> q;
			for (int i = 0; i < Vnum; i++) {
				if (Vvisit[i] == 1) {
					visit[virus[i].x][virus[i].y] = 1;
					q.push({ virus[i].x,virus[i].y,0 });
				}
				else {
				//	visit[virus[i].x][virus[i].y] = 1;
				}
			}
			for (int i = 0; i < wallcnt; i++) {
				visit[wall[i].x][wall[i].y] = 1;
			}
			int tempans = 0;
			while (!q.empty()) {
				int r = q.front().x;
				int c = q.front().y;
				int cnt = q.front().cnt;
				q.pop();
				for (int i = 0; i < 4; i++) {
					int nr = r + dr[i];
					int nc = c + dc[i];
					if (nr < 0 || nc < 0 || nr >= n || nc >= n) {
						continue;
					}
					if (map[nr][nc] == 0) {
						if (visit[nr][nc] == 0) {
							visit[nr][nc] = visit[r][c] + 1;
							tempans = max(tempans, visit[nr][nc]);
							q.push({ nr,nc,cnt + 1 });
						}
					}
					if (map[nr][nc] == 2) {
						if (visit[nr][nc] == 0) {
							visit[nr][nc] = visit[r][c]+1;
							q.push({ nr,nc,cnt + 1 });
						}
					}
				}
			}
			//총 갯수 n*n 벽 갯수 wallcnt 바이러스 개수 Vcnt 퍼진 바이러스 nowcnt
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j] == 0 && visit[i][j] == 0)
						return;
				}
			}
			ans = min(tempans, ans);
		}
		return;
	}


	Vvisit[now] = 1;
	dfs(now + 1, cnt + 1);
	Vvisit[now] = 0;
	dfs(now + 1, cnt);
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				virus[Vcnt].x = i;
				virus[Vcnt].y = j;
				Vcnt++;
				Vnum++;
			}
			if (map[i][j] == 1) {
				wall[wallcnt].x = i;
				wall[wallcnt].y = j;
				wallcnt++;
			}
		}
	}
	int flag = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0)
				flag = 1;
		}
		if (flag == 1)
			break;
	}
	if (flag == 1)
	{
		dfs(0, 0);
		if (ans == 987654321) {
			cout << -1 << endl;
		}
		else {
			cout << ans - 1 << endl;
		}
	}
	else {
		cout << 0 << endl;
	}
}