[14502] 연구소

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

바이러스를 연구하던 연구소에서 바이러스가 유출됐다.

우리는 빈 공간에 벽을 세워 바이러스의 확산을 막을 수 있다.

벽은 반드시 3개를 세워야한다.

연구소 지도에 바이러스 위치와 벽, 빈 공간이 주어졌을 때

어느 곳에 벽을 세워야 바이러스위 확산을 최대한으로 막을 수 있냐고 묻는 문제이다.

지도의 크기는 최대 10*10 이므로 완전 탐색을 이용해 풀면 된다.

나는 벡터를 하나 만들어 빈 공간의 위치를 저장해두고

그 벡터의 아이템 중 3개를 골라 벽을 세우는 방식으로 코드를 작성했다.

벽을 세운 후 바이러스(2)를 찾아 dfs를 진행하고 남아있는 빈 공간의 개수의 합을

최대로 갱신해가면서 저장했다.

끝.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m, arr[10][10], temp[10][10], maxi;
bool disc[110], visit[10][10];
vector<pair<int, int> > blank;
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n&&ny >= 0 && ny < m && !visit[nx][ny] && !temp[nx][ny]) {
            visit[nx][ny] = 1;
            temp[nx][ny] = 2;
            dfs(nx, ny);
        }
    }
}
 
void func(int num, int r) {
    if (num >= (int)blank.size()) {
        if (r == 0) {
            memcpy(temp, arr, sizeof(arr));
            for (int i = 0; i < (int)blank.size(); i++) {
                if (disc[i]) {
                    int x = blank[i].first;
                    int y = blank[i].second;
                    temp[x][y] = 1;
                }
            }
            memset(visit, 0, sizeof(visit));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (temp[i][j] == 2 && !visit[i][j]) {
                        visit[i][j] = 1;
                        dfs(i, j);
                    }
                }
            }
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!temp[i][j]) cnt++;
                }
            }
            maxi = max(maxi, cnt);
        }
        return;
    }
    if (r > 0) {
        disc[num] = 1;
        func(num + 1, r - 1);
        disc[num] = 0;
    }
    func(num + 1, r);
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 0) {
                blank.push_back({ i,j });
            }
        }
    }
    maxi = 0;
    func(0, 3);
    printf("%d\n", maxi);
 
    return 0;
}