연구소

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

14502번: 연구소

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

int check[81];
vector<pair<int, int> > Empty;
vector < pair<int, int> > Virus;
int visit[9][9];
int board[9][9];
int copyBoard[9][9];
int n, m;
int answer = 0;

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

void BFS(int y, int x) {
	queue<pair<int, int> > Q;
	Q.push(make_pair(y, x));
	visit[y][x] = 1;
	while (!Q.empty()) {
		int tmp_y = Q.front().first;
		int tmp_x = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = tmp_y + dy[i];
			int nx = tmp_x + dx[i];
			if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) {
				if (visit[ny][nx] == 0 && copyBoard[ny][nx] == 0) {
					Q.push(make_pair(ny, nx));
					visit[ny][nx] = 1;
					copyBoard[ny][nx] = 2;
				}
			}
		}
	}
}

void spread() {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			copyBoard[i][j] = board[i][j];
		}
	}
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < Empty.size(); i++) {
		if (cnt == 3) break;
		if (check[i] == 1) {
			int y = Empty[i].first;
			int x = Empty[i].second;
			copyBoard[y][x] = 1;
			cnt++;
		}
	}
	for (int i = 0; i < Virus.size(); i++) {
		int y = Virus[i].first;
		int x = Virus[i].second;
		BFS(y, x);
	}
	int s_cnt = 0; //안전 구역 수
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (copyBoard[i][j] == 0) {
				s_cnt++;
			}
		}
	}
	answer = max(answer, s_cnt);
}

void makeWall(int idx, int cnt) {
	if (cnt == 3) {
		spread();
		return;
	}
	else {
		for (int i = idx; i < Empty.size(); i++) {
			if (check[i] == 1) continue;
			check[i] = 1;
			makeWall(i, cnt+1);
			check[i] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) Empty.push_back(make_pair(i, j));
			else if (board[i][j] == 2) Virus.push_back(make_pair(i, j));
		}
	}
	makeWall(0,0);
	cout << answer<<"\n";
	return 0;
}

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

// 0빈칸 1벽 2바이러스

int n, m;
int map[8][8];
int copy_map[8][8];
int visited[8][8];
vector<pair<int, int> > virus;
vector<pair<int, int> > empty_space;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int answer = 0;
int check[81];

void copyMap() {
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			copy_map[y][x] = map[y][x];
		}
	}
}

void initialize_visit() {
	for (int y = 0; y < 8; y++) {
		for (int x = 0; x < 8; x++) {
			visited[y][x] = 0;
		}
	}
}

int spread() {
	copyMap();
	int cnt = 0;
	for (int i = 0; i < empty_space.size(); i++) {
		if (cnt == 3) break;
		if (check[i] == 1) {
			copy_map[empty_space[i].first][empty_space[i].second] = 1;
			cnt++;
		}
	}
	initialize_visit();
	queue<pair<int, int> > Q;
	for (int i = 0; i < virus.size(); i++) {
		Q.push(make_pair(virus[i].first, virus[i].second));
	}
	while (!Q.empty()) {
		int vy = Q.front().first; int vx = Q.front().second;
		Q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = vy + dy[d]; int nx = vx + dx[d];
			if (copy_map[ny][nx] == 0 && ny >= 0 && ny < n && nx >= 0 && nx < m) {
				copy_map[ny][nx] = 2;
				Q.push(make_pair(ny, nx));
			}
		}
	}
	int ret = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (copy_map[y][x] == 0) ret++;
		}
	}
	return ret;
}



void makeWall(int idx, int cnt) {
	if (cnt == 3) {
		int candi = spread();
		answer = max(answer, candi);
	}
	else {
		for (int i = idx; i < empty_space.size(); i++) {
			check[i] = 1;
			makeWall(i + 1, cnt + 1);
			check[i] = 0;
		}
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
			if (map[y][x] == 0) empty_space.push_back(make_pair(y, x));
			if (map[y][x] == 2) virus.push_back(make_pair(y, x));
		}
	}
	makeWall(0, 0);
	cout << answer << "\n";
	return 0;
}