14502 연구소

전형적인 전체탐색 문제이다. 

Solution 

1. 재귀함수를 통해 벽을 세울 위치를 3개를 탐색한다.
2. 3개가 탐색되면, 바이러스를 퍼지는 것을 시뮬레이션 돌려서 완전공간을 확인한다. 

 

Key Point

상관은 없지만, 시간을 줄이기 위해서 check함수로 통해 중복연산을 줄였다. 하지만, 이를 하지 않아도 성공할 수 있다. 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
using namespace std;

#define INF 10000000
typedef struct A {
	int i, j;
};
vector<vector<int>> map;
int n, m;
queue<A> list;
int wall_number = 0;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int max_zero = 0;
int check[8][8][8][8][8][8];

void cal_viru() {
	vector<vector<int>> b(map);
	queue<A> li = list;
	int viru_number = li.size();
	while (!li.empty()) {
		int i = li.front().i;
		int j = li.front().j;
		li.pop();
		for (int k = 0; k < 4; k++) {
			if (i + dx[k] >= n || i + dx[k] < 0)
				continue;
			if (j + dy[k] >= m || j + dy[k] < 0)
				continue;
			if (b[i + dx[k]][j + dy[k]] == 0) {
				viru_number++;
				b[i + dx[k]][j + dy[k]] = 2;
				li.push({ i + dx[k],j + dy[k] });
			}
		}
	}
	int box = n * m - (wall_number + 3) - viru_number;
	if (box > max_zero)
		max_zero = box;
}

bool cmp(const A& a, const A& b)
{
	if (a.i < b.i) return true; // 제일 먼저 f를 기준으로 오름차순 정렬
	else if (a.i == b.i) // 만약에 f가 같다면
	{
		if (a.j < b.j) return true; // t를 기준으로 오름차순 정렬
		else false;
	}

	// 각 경우에 대하여 else를 고려할 필요가 없다.
	return false;
}
void search_wall(vector<A> b) {
	if (b.size() == 3) {
		sort(b.begin(),b.end(),cmp);
		if (check[b[0].i][b[0].j][b[1].i][b[1].j][b[2].i][b[2].j] == 1)
			return;
		cal_viru();
		check[b[0].i][b[0].j][b[1].i][b[1].j][b[2].i][b[2].j] = 1;
		return;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				b.push_back({ i, j });
				search_wall(b);
				b.pop_back();
				map[i][j] = 0;
			}
		}
	}
}
int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		vector<int> a;
		map.push_back(a);
		for (int j = 0; j < m; j++) {
			int box;
			cin >> box;
			map[i].push_back(box);
			if (map[i][j] == 2)
				list.push({ i,j });
			if (map[i][j] == 1)
				wall_number++;
		}
	}
	vector<A> c;
 	search_wall(c);
	cout << max_zero;
	return 0;
}

 

 

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

14502번: 연구소