연구소

이문제는 "조합", "DFS/BFS", "Connected Component" 세가지를 통해 로직을 3단계로 풀면 풀리는 문제이다.

마지막에 connected Component를 사용하는것은 알겠고 구현은함.

그런데 그전 단계인 "벽"을 세우고 바이러스가 퍼졌을 때의 상황을 못 구현했다.

먼저 벽을 "효율적"으로 먼저 세우는게 아니라

"무식하게" 벽을 먼저 세울 생각부터 해야한다.

그 다음에 효율적으로 세울 방법을 생각해야한다.

문제에 최대 범위가 8이기 때문에 8x8 일 경우

벽 3개를 순서에 상관없이 세울 수 있는 경우의 수는 64 C 3이다. (콤비네이션)

벽들의 후보들중에서 세개를 골라서 벽을 세워두고

DFS로 바이러스르르 퍼지게 한뒤에 아직 안전지대인 부분의 갯수를 골라내면은 된다.

cpp 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"

int n, m, ret = -1;
int visited[10][10];

vector<vector<int>> vec;
vector<pair<int, int>> wallList;
vector<pair<int, int>> virusList;

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

void CM()
{
	cin >> n >> m;
	vec.resize(n);
	for (int i = 0; i < n; ++i)
		vec[i].resize(m);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> vec[i][j];
			if (vec[i][j] == 2) virusList.push_back({ i, j });
			if (vec[i][j] == 0) wallList.push_back({ i, j });
		}
	}
}

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || vec[y][x] == 1 || visited[y][x])
		return false;
	return true;
}

void DFS(int y, int x)
{
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		visited[ny][nx] = true;
		DFS(ny, nx);
	}
}

int Solve()
{
	fill(&visited[0][0], &visited[9][10], 0);
	// memset(visited, 0, sizeof(visited));
	for (pair<int, int> b : virusList)
	{
		visited[b.first][b.second] = true;
		DFS(b.first, b.second);
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (vec[i][j] == 0 && visited[i][j] == false)
				++cnt;
		}
	}
	return cnt;
}

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

	CM();
	for (int i = 0; i < wallList.size(); ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			for (int k = 0; k < j; ++k)
			{
				vec[wallList[i].first][wallList[i].second] = 1;
				vec[wallList[j].first][wallList[j].second] = 1;
				vec[wallList[k].first][wallList[k].second] = 1;
				ret = max(ret, Solve());
				vec[wallList[i].first][wallList[i].second] = 0;
				vec[wallList[j].first][wallList[j].second] = 0;
				vec[wallList[k].first][wallList[k].second] = 0;
			}
		}
	}

	cout << ret << endl;
	return 0;
}