백준 #14502 [c++]

 

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

using namespace std;

int n, m; // 세로 가로
int maxCount = 0; // 바이러스 max값
int lab[8][8];
int lab_copy[8][8];
bool visit[8][8];
bool build[8][8];

int virusCount = 0;
int virusX[10];
int virusY[10];

// 상하좌우
int dir_y[4] = { 1, -1, 0, 0 };
int dir_x[4] = { 0, 0, -1, 1 };

void init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
lab_copy[i][j] = lab[i][j];
visit[i][j] = false;
}
}
}

void findMaxCount() {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (lab_copy[i][j] == 0) count++;
}
}
if (count > maxCount) maxCount = count;
}

void spread(int y, int x) {

queue<pair<int, int>> q;
q.push(make_pair(y, x));
visit[y][x] = true;

while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int next_y = y + dir_y[i];
int next_x = x + dir_x[i];
// 다음 좌표가 범위내라면
if (next_y >= 0 && next_x >= 0 && next_y < n && next_x < m) {
// 다음 좌표가 방문하지 않았고 0이라면
if (!visit[next_y][next_x] && lab_copy[next_y][next_x] == 0) {
lab_copy[next_y][next_x] = 2;
visit[next_y][next_x] = true;
q.push(make_pair(next_y, next_x));
}
}
}
}
}

void buildFence(int cnt) {
if (cnt == 3) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (build[i][j] == true) {
lab_copy[i][j] = 1;
}
}
}

for (int k = 0; k < virusCount; k++) {
spread(virusY[k], virusX[k]);
}
findMaxCount();

init();
return;
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (lab_copy[i][j] == 0 && build[i][j] == false) {
build[i][j] = true;
buildFence(cnt + 1);
build[i][j] = false;
}
}
}
}

int main() {

cin >> n >> m;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> lab[i][j];
if (lab[i][j] == 2) {
virusY[virusCount] = i;
virusX[virusCount] = j;
virusCount++;
}
}
}


init();
buildFence(0);

cout << maxCount;

/*
// 출력 테스트
cout << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout <<  lab_copy[i][j] << ' ';
}
cout << endl;
}
*/

return 0;
}