#14502. 연구소

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

1. 문제 이해

 벽을 3개 세웠을때, 바이러스가 퍼지고, 그후 바이러스에 전염되지 않은지역을 세는 문제입니다. 이때, 전염되지 않은 지역이 최대가 되는 경우를 알아내는 문제입니다. 

2. 접근 방법

 n이 8보다 작은수 이므로 완전 탐색으로 해결했습니다.

[1단계] dfs로 벽 세우기 (for문을 사용한 완전 탐색)

[2단계] 벽이 3개가 됐을때, bfs로 바이러스 확장시키기

[3단계] 바이러스를 퍼지기 전으로 회복시키면서 전염이 안된 지역 세어주기

3. 문제 해결

#include <cstdio>
#include <vector>
#include <queue>
#define MAX_SIZE 8
 
using namespace std;
 
int n, m;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int map[MAX_SIZE][MAX_SIZE];    // 1:벽, 2:바이러스
int visit[MAX_SIZE][MAX_SIZE];
vector <pair <int, int> > virus;
int _max = 0;
 
int recovery_map(int(* a)[MAX_SIZE], int(* b)[MAX_SIZE]) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0) ret++;
            b[i][j] = a[i][j];
        }
    }
    return ret;
}
 
void copy_map(int(* a)[MAX_SIZE], int (* b)[MAX_SIZE]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = b[i][j];
        }
    }
}
 
void bfs() {
    queue <pair<int, int> >q;
    for (int i = 0; i < virus.size(); i++) {
        q.push(virus[i]);
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if (map[ny][nx] != 0) continue;
 
            map[ny][nx] = 2;
            q.push(make_pair(nx, ny));
        }
 
    }
}
 
void make_wall(int x, int y, int d) {
    map[y][x] = 1;
    visit[y][x] = 1;
 
    if (d == 3) {
 
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
        bfs();
        int buf = recovery_map(tmp, map);
        _max = _max < buf ? buf : _max;
 
        map[y][x] = 0;
        visit[y][x] = 0;
        return;
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != 0 || visit[i][j]) continue;
            make_wall(j, i, d + 1);
        }
    }
    map[y][x] = 0;
    visit[y][x] = 0;
 
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) virus.push_back(make_pair(j, i));
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != 0) continue;
            make_wall(j, i, 1);
        }
    }
 
    printf("%d\n", _max);
    return 0;
}