백준 17142번 : 연구소

sol : 102' 42''

• 수행 시간 : 16ms
• 메모리 : 2044KB

Learnings

• 조합 구현

void SelectV(vector<pair<int, int>> curV, int r, int index, int depth) {
	if (r == 0) {
		answer = min(answer, Simulate(curV));
		return;
	}

	else if (depth == viruses.size()) return;
	else {
		curV[index] = viruses[depth];
		SelectV(curV, r - 1, index + 1, depth + 1);
		SelectV(curV, r, index, depth + 1);
	}
}

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

#define MAX_N 50
#define EMPTY 0
#define WALL 1
#define VIRUS 2

int n, m;
int grid[MAX_N][MAX_N];
int timeGrid[MAX_N][MAX_N];
// 상, 하, 좌, 우
int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

vector<pair<int, int>> viruses;
int answer = INT_MAX;

void Init() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];

			if (grid[i][j] == VIRUS) {
				viruses.push_back({ i, j });
			}
		}
	}
}

void InitTimeGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			timeGrid[i][j] = -1;
		}
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

int Simulate(const vector<pair<int, int>>& curV) {
	queue<pair<int, int>> q;
	InitTimeGrid();

	// 멀티소스 BFS 시작
	for (int i = 0; i < m; i++) {
		int r = curV[i].first;
		int c = curV[i].second;
		q.push({ r, c });
		timeGrid[r][c] = 0;
	}

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0];
			int nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (grid[ni][nj] == WALL) continue;
			if (timeGrid[ni][nj] != -1) continue;

			timeGrid[ni][nj] = timeGrid[ci][cj] + 1;
			q.push({ ni, nj });
		}
	}

	int maxTime = 0;

	// 빈 칸만 대상으로 전부 퍼졌는지 확인 + 최대 시간 계산
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == EMPTY) {
				if (timeGrid[i][j] == -1) return INT_MAX;
				maxTime = max(maxTime, timeGrid[i][j]);
			}
		}
	}

	return maxTime;
}

void SelectV(vector<pair<int, int>>& curV, int r, int index, int depth) {
	if (r == 0) {
		answer = min(answer, Simulate(curV));
		return;
	}

	if (depth == (int)viruses.size()) return;

	curV[index] = viruses[depth];
	SelectV(curV, r - 1, index + 1, depth + 1);
	SelectV(curV, r, index, depth + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Init();

	vector<pair<int, int>> activatedV(m);
	SelectV(activatedV, m, 0, 0);

	if (answer == INT_MAX) cout << -1;
	else cout << answer;

	return 0;
}