연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int map[51][51];
int n, m;
int answer = 2147000000;

int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };

struct POS {
	int y, x, time;
}; // 바이러스

int pos_size;
POS pos[10];

int bfs(int pick[]) {
	int empty_cnt = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (map[y][x] == 0) empty_cnt++;
		}
	}
	queue<POS> q;
	int visited[51][51] = { 0, };
	for (int i = 0; i < m; i++) {
		q.push(pos[pick[i]]);
		visited[pos[pick[i]].y][pos[pick[i]].x] = 1;
	}
	while (!q.empty()) {
		POS cur = q.front(); q.pop();
		if (map[cur.y][cur.x] == 0) empty_cnt--;
		if (empty_cnt == 0) return cur.time;
		POS next;
		next.time = cur.time + 1;
		for (int dir = 0; dir < 4; dir++) {
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) continue;
			if (visited[next.y][next.x] == 0 && map[next.y][next.x] != 1) {
				q.push(next);
				visited[next.y][next.x] = 1;
			}
		}
	}
	return 2147000000;
}

void DFS(int last_pick, int pick_cnt, int pick[]) {
	if (pick_cnt == m) {
		int candi = bfs(pick);
		answer = min(answer, candi);
	}
	else {
		for (int i = last_pick + 1; i < pos_size; i++) {
			pick[pick_cnt] = i;
			DFS(i, pick_cnt + 1, pick);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
			if (map[y][x] == 2) {
				pos[pos_size].y = y;
				pos[pos_size].x = x;
				pos[pos_size].time = 0;
				pos_size++;
			}
		}
	}
	int pick[10] = { 0, }; //활성 바이러스
	DFS(-1, 0, pick);
	if (answer == 2147000000) answer = -1;
	cout << answer << "\n";
	return 0;
}