[백준][C++] 14502: 연구소

문제 링크: https://www.acmicpc.net/problem/14502

 

브루트포스 문제입니다.

벽을 3군데에 세우는 모든 경우의 수에 대해서 바이러스를 퍼트린 후 칸을 세봐서 가장 많은 칸이 남은 경우의 칸 수를 구하면 됩니다.

연구실이 전부 빈 칸이라고 가정했을 때 벽을 3군데에 세우는 모든 경우의 수는 \(\displaystyle\frac{64!}{61!\times3!} = \frac{64 \times 63 \times 62}{6} = 41664\)가 되니까 적당히 다 돌려볼 수 있습니다.

바이러스를 퍼트리는 건 dfs, bfs중에 골라서 해주면 됩니다

#include <bits/stdc++.h>
using namespace std;


enum cell { empty, wall, virus };
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int n, m;
int board[8][8];
vector<pair<int, int>> virus_pt;
int max_area;


constexpr bool in_range(int y, int x) {
	return y>=0 && y<n && x>=0 && x<m;
}

void bruteforce(int current, vector<int>& picked, int toPick) {
	if (toPick == 0) {
		int copied[8][8];
		memcpy(copied, board, sizeof(board));

		for (auto& idx : picked) {
			int row = idx / m;
			int col = idx % m;
			copied[row][col] = cell::wall;
		}

		queue<pair<int, int>> q;
		for (auto& p : virus_pt)
			q.push(p);

		while (!q.empty()) {
			auto [y, x] = q.front();
			q.pop();

			for (int i = 0; i < 4; ++i) {
				int ny = y + dy[i];
				int nx = x + dx[i];

				if (in_range(ny, nx) && copied[ny][nx] == cell::empty) {
					copied[ny][nx] = cell::virus;
					q.emplace(ny, nx);
				}
			}
		}

		int cnt = 0;
		for (int i=0; i<n; ++i)
			for (int j=0; j<m; ++j)
				if (copied[i][j] == cell::empty)
					++cnt;

		max_area = max(max_area, cnt);

		return;
	}
	
	if (current == n * m)
		return;

	int row = current / m;
	int col = current % m;
	if (board[row][col] == cell::empty) {
		picked.push_back(current);
		bruteforce(current + 1, picked, toPick - 1);
		picked.pop_back();
	}
	bruteforce(current + 1, picked, toPick);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			cin >> board[i][j];
			if (board[i][j] == cell::virus)
				virus_pt.emplace_back(i, j);
		}

	vector<int> v;
	bruteforce(0, v, 3);

	cout << max_area;

	return 0;
}

벽을 세울 칸을 고르는건 백트래킹으로 했고, 바이러스는 bfs로 퍼트렸습니다.