백준 14502번 연구소 C/C++ 풀이

acmicpc.net/problem/14502

14502번: 연구소

 

문제에서 사용하는 범위의 크기가 크지 않아서 전체 map 안에서 벽과 바이러스가 없는 부분 재귀함수를 이용해서 3가지를 선택하고 그에 따라 안전 범위가 몇 개 생기는지를 구했다.

 

#include <stdio.h>
#include <utility>

using namespace std;

FILE* in = stdin;

#define MAX 8

int n, m;
int map[MAX][MAX];
int cnt;
int max = 0;
int path[3];
bool checked[MAX * MAX];
pair<int, int> virus[10];

//바이러스 확산을 구현하기 위한 함수, 범위 지정에 조심
void color(int x, int y) {
	if (x + 1 < n && y < m && x + 1 >= 0 && y >= 0)
	{
		if (map[x + 1][y] == 0)
		{
			map[x + 1][y] = 2;
			color(x + 1, y);
		}
	}
	if (x < n && y + 1 < m && x >= 0 && y + 1 >= 0)
	{
		if (map[x][y + 1] == 0)
		{
			map[x][y + 1] = 2;
			color(x, y + 1);
		}
	}
	if (x - 1 < n && y < m && x - 1 >= 0 && y >= 0)
	{
		if (map[x - 1][y] == 0)
		{
			map[x - 1][y] = 2;
			color(x - 1, y);
		}
	}
	if (x < n && y - 1 < m && x >= 0 && y - 1 >= 0)
	{
		if (map[x][y - 1] == 0)
		{
			map[x][y - 1] = 2;
			color(x, y - 1);
		}
	}
	return;
}

//3가지를 정한 이후 확산 시켰을 때 안전지역이 얼마나 남는지를 구하는 함수
void diff(int a, int b, int c) {
	int a_x = a / m; int a_y = a % m; int b_x = b / m; int b_y = b % m; int c_x = c / m; int c_y = c % m;
	map[a_x][a_y] = 1; map[b_x][b_y] = 1; map[c_x][c_y] = 1;
	for (int i = 0; i < cnt; i++)
		color(virus[i].first, virus[i].second);
	int ans = 0;
	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 0)
				ans++;
		}
	if (ans > max)
		max = ans;
	map[a_x][a_y] = 0; map[b_x][b_y] = 0; map[c_x][c_y] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 2)
				map[i][j] = 0;
		}
	for (int i = 0; i < cnt; i++)
		map[virus[i].first][virus[i].second] = 2;
}

//벽을 설치하는 3가지 구역을 선택하는 함수
void combi(int idx, int sel) {
	if (sel == 3)
	{
		diff(path[0], path[1], path[2]);
		return;
	}
	if (idx == n * m)
		return;
	if (map[idx/m][idx%m] == 0)
	{
		path[sel] = idx;
		combi(idx + 1, sel + 1);
	}
	combi(idx + 1, sel);
	return;
}


int main() {
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			fscanf(in, "%d", &map[i][j]);
	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 2)
			{
				virus[cnt] = make_pair(i, j);
				cnt++;
			}
		}
	combi(0, 0);
	printf("%d", max);
	return 0;
}