[백준] 골드4-연구소 C++ 14502번

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

 

// 로직 1번 - 최대 64개 중 3개를 골라 벽을 세운다(조합)

// 로직 2번 - 최대 64개 중 바이러스(2)가 있는 곳으로부터 바이러스를 퍼트린다(dfs, bfs)

// 로직 3번 - 최대 64개 중 바이러스가 없는 안전구역(0)의 넓이를 구한다(counting)

// 최대 시간복잡도는 대충 64C3 * (64 + 64) ~= 5,000,000으로 시간복잡도 천만 이하는 효율 고려하지 않고 무식하게 푼다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
int adj[8][8];
bool visited[8][8];
vector<pair<int, int>> wall;
vector<pair<int, int>> virus;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int ret;

void vir(int y, int x)
{
	visited[y][x] = 1;

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

		if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
		if (visited[ny][nx]) continue;
		if (adj[ny][nx] == 1) continue;

		vir(ny, nx);
	}
	return;
}

int solve()
{
	fill(&visited[0][0], &visited[0][0] + 8 * 8, 0);
	for (pair<int, int> i : virus)
	{
		vir(i.first, i.second);
	}

	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (adj[i][j] == 0 && !visited[i][j])
				cnt++;
		}
	}
	return cnt;
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> adj[i][j];
			if (adj[i][j] == 2) virus.push_back({ i,j });
			if (adj[i][j] == 0) wall.push_back({ i,j });
		}
	}

	for (int i = 0; i < wall.size(); i++)
	{
		for (int j = 0; j < i; j++)
		{
			for (int k = 0; k < j; k++)
			{
				adj[wall[i].first][wall[i].second] = 1;
				adj[wall[j].first][wall[j].second] = 1;
				adj[wall[k].first][wall[k].second] = 1;
				
				ret = max(ret, solve());

				adj[wall[i].first][wall[i].second] = 0;
				adj[wall[j].first][wall[j].second] = 0;
				adj[wall[k].first][wall[k].second] = 0;
			}
		}
	}
	cout << ret;

	return 0;
}