백준 - 연구소 3 [17142]

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

using namespace std;
bool g_check = false;
int result;
int map[50][50];
bool visit[50][50];
queue < pair<int, int>> v_pos;

int bfs(int mapsize, int zero) {
	int i;
	int j;
	int time = 0;
	bool check = false;


	while (!v_pos.empty()) {
		time++;
		check = false;
		queue<pair<int, int>> temp;
		pair<int, int> q;

		while (!v_pos.empty()) {
			q = v_pos.front();
			i = q.first;
			j = q.second;
			visit[i][j] = true;

			if (i > 0) {
				if (!visit[i - 1][j] && map[i - 1][j] != 1) {
					temp.push(make_pair(i - 1, j));
					if (map[i - 1][j] == 0)
						zero--;
					check = true;
				}
				visit[i - 1][j] = true;
			}
			if (j > 0) {
				if (!visit[i][j - 1] && map[i][j - 1] != 1) {
					temp.push(make_pair(i, j - 1));
					if (map[i][j - 1] == 0)
						zero--;
					check = true;
				}
				visit[i][j - 1] = true;
			}
			if (j < mapsize - 1) {
				if (!visit[i][j + 1] && map[i][j + 1] != 1) {
					temp.push(make_pair(i, j + 1));
					if (map[i][j + 1] == 0)
						zero--;
					check = true;
				}
				visit[i][j + 1] = true;
			}
			if (i < mapsize - 1) {
				if (!visit[i + 1][j] && map[i + 1][j] != 1) {
					temp.push(make_pair(i + 1, j));
					if (map[i + 1][j] == 0)
						zero--;
					check = true;

				}
				visit[i + 1][j] = true;
			}
			if (zero == 0)
				return time;

			v_pos.pop();
		}

		if (!check)
			time--;
		if (g_check) {
			if (result == time)
				return -1;
		}
		v_pos = temp;

	}

	return -1;
}

int main() {
	int n, vnum, v_posi_pos_num = 0;
	vector < pair<int, int>> v_posi_pos;
	vector<int> ind;
	int time = 0;
	int zero = 0;
	int num;

	cin >> n;
	cin >> vnum;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> num;
			map[i][j] = num;
			if (num == 0) {
				zero++;
			}
			if (num == 2) {
				v_posi_pos.push_back(make_pair(i, j));
				v_posi_pos_num++;
			}
		}
	}
	if (zero == 0) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < v_posi_pos_num - vnum; i++)
		ind.push_back(0);
	for (int i = 0; i < vnum; i++)
		ind.push_back(1);

	do {
		for (int i = 0; i < v_posi_pos_num; i++)
			if (ind[i] == 1) {
				v_pos.push(make_pair(v_posi_pos[i].first, v_posi_pos[i].second));
			}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				visit[i][j] = false;

		time = bfs(n, zero);

		if (time != -1) {
			g_check = true;
			result = time;
		}

		while (!v_pos.empty())
			v_pos.pop();

	} while (next_permutation(ind.begin(), ind.end()));


	if (g_check == false)
		cout << -1;
	else
		cout << result;

	return 0;
}