14502 - 연구소('17 상반기 삼성기출).cpp

#include <stdio.h>
#include <iostream>
#include <stack>
#include <cstring>
#include <queue>

#define ll long long int
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(b):(a)
#define pii pair<int , int>
#define x first
#define y second

using namespace std;

int matrix[10][10];
int n, m;
int w = 0;
int v = 0;
int nx[4] = { 1, 0, 0,-1 }, ny[4] = { 0, 1, -1, 0 };
pii virus[12];

int bfs(pii a, pii b, pii c) {
	if (a == b || b == c || c == a) return 0;
	int mat[12][12];
	queue<pii> q;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
			mat[i][j] = matrix[i][j];

	mat[a.y][a.x] = 1;
	mat[b.y][b.x] = 1;
	mat[c.y][c.x] = 1;

	for (int i = 0; i < v; i++) q.push(virus[i]);

	int nv = 0;

	while (!q.empty())
	{
		pii cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int x = cur.x + nx[i], y = cur.y + ny[i];

			if (x >= 0 && y >= 0 && x < m && y < n &&
				mat[y][x] == 0)
			{
				mat[y][x] = 2;
				q.push(pii(x, y));
				nv++;
			}
		}
	}

	return n*m - v - nv - w - 3;
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &matrix[i][j]);
			if (matrix[i][j] == 2) virus[v++] = pii(j,i);
			if (matrix[i][j] == 1) w++;
		}
	}

	int ans = 0;

	for(int a = 0; a < n; a++)
		for (int b = 0; b < m; b++)
			for (int c = 0; c < n; c++)
				for (int d = 0; d < m; d++)
					for (int e = 0; e < n; e++)
						for (int f = 0; f < m; f++)
						{
							if (matrix[a][b] ||
								matrix[c][d] ||
								matrix[e][f])
								continue;

							ans = MAX(ans, bfs(pii(b, a), pii(d, c), pii(f, e)));
						}

	printf("%d\n", ans);
	return 0;
}