14502번_연구소_BOJ

문제 링크

14502번 연구소 : https://www.acmicpc.net/problem/14502

문제 설명 및 해결 아이디어

3개의 벽을 세워 바이러스가 퍼질 수 없는 안전영역 크기의 최대값을 출력하는 문제이다. 

기본 아이디어는 완점탐색을 하면서 바이러스가 퍼질수 있는 영역의 최소값을 구하는 것이다.

3개의 벽을 세울 수 있는 모든 경우의 수를 돌린다. 각 경우마다 Depth-First Search(DFS)를 수행하여 퍼질 수 있는 영역의 크기를 계산해나간다.

바이러스가 퍼질 수 있는 영역 크기의 최소값을 찾은 후, 전체 크기에서 벽(1)의 개수, 새로 세운 벽 3개, 바이러스 퍼진 영역 크기의 최소값을 빼주면 된다.

코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_S 10
#define INF 987654321
 
int map[MAX_S][MAX_S];
int visit[MAX_S][MAX_S];
int n, m, wall;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
bool chk(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
 
int dfs(int x, int y) {
    int res = 1;
    visit[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (chk(nx, ny) && !visit[nx][ny] && !map[nx][ny]) {
            res += dfs(nx, ny);
        }
    }
    return res;
}
 
int spreadVirus_func(int ix, int iy, int jx, int jy, int kx, int ky) {
    map[ix][iy] = 1, map[jx][jy] = 1, map[kx][ky] = 1;
    memset(visit, 0, sizeof(visit));
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == 2 && !visit[i][j])
                res += dfs(i, j);
        }
    }
    map[ix][iy] = 0, map[jx][jy] = 0, map[kx][ky] = 0;
    return res;
}
 
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] == 1)
                wall++;
        }
    }
    int temp = INF;
 
    for (int ix = 0; ix < n; ++ix) {
        for (int iy = 0; iy < m; ++iy) {
            for (int jx = 0; jx < n; ++jx) {
                for (int jy = 0; jy < m; ++jy) {
                    for (int kx = 0; kx < n; ++kx) {
                        for (int ky = 0; ky < m; ++ky) {
                            if (map[ix][iy] || map[jx][jy] || map[kx][ky])
                                continue;
                            temp = min(temp, spreadVirus_func(ix, iy, jx, jy, kx, ky));
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", n*m - 3 - wall - temp);
    return 0;
}