연구소 3 C++

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

17142번: 연구소 3

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

using namespace std;
const int MAX = 55;
struct MOVE { int x, y; };
MOVE mv[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int map[MAX][MAX]; //0:빈칸, 1:벽, 2:바이러스
int answer = 987654321;
int n,m;
vector<pair<int,int>> vr;
//0,0       1,5       4,3
void FindMinTime(vector<pair<int,int>> t) {
	int tmp_map[MAX][MAX];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1)	tmp_map[i][j] = -2;
			else
				tmp_map[i][j] = -1;
		}
	}
	
	int tmp_answer=0;
	struct INFO { int x, y, count; };
	queue<INFO> q;
	for (int i = 0; i < t.size(); i++) {
		q.push({ t[i].first, t[i].second ,0 });
		tmp_map[t[i].first][t[i].second] = 0;
	}

	while (!q.empty()) {
		int mi = q.front().x;
		int mj = q.front().y;
		int c = q.front().count;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int movei = mi + mv[k].x;
			int movej = mj + mv[k].y;

			if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
				if (tmp_map[movei][movej] == -1) {
					if (find(vr.begin(), vr.end(), make_pair(movei,movej)) == vr.end())	tmp_answer = max(tmp_answer, c + 1);
					tmp_map[movei][movej] = c + 1;
					q.push({ movei,movej,c + 1 });
				}
			}
		}
	}
	
	bool flag = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (tmp_map[i][j] == -1) {
				flag = false;
				break;
			}
		}
		if (flag == false)	break;
	}

	if (flag == true) {
		answer = min(answer, tmp_answer);
	}
}

void SelectVr(int index,vector<pair<int, int>> t) {
	if (t.size() == m) {
		FindMinTime(t);
	}

	for (int i = index; i < vr.size(); i++) {
		t.push_back(vr[i]);
		SelectVr(i + 1, t);
		t.pop_back();
	}
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				vr.push_back(make_pair(i, j));
			}
		}
	}

	vector<pair<int, int>> tmp;
	SelectVr(0,tmp);

	if (answer == 987654321) cout << -1 << endl;
	else cout << answer << endl;
}