[BOJ] #14502 연구소

시간 제한	메모리 제한	정답 비율
2 초	512 MB	54.661 %

14502번: 연구소

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

로 나타내며, 바이러스가 퍼저나가는 것을 막기위해 3개의 벽을 세워야 한다. 
이 때 0인 부분을 안전 영역이라하고 안전 영역 크기의 최댓값을 구하는 것이다.

처음 아이디어는 2를 기준으로 벽을 하나씩 세워볼까 했다가 어쨌든 모든 경우를 다 봐야하므로 0 인 칸들을 모두 탐색하여 벽을 세우는 방법을 생각했다.

 

메모리	시간
1180 KB	44 ms

#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> p;
int di[] = { 0,0,1,-1 };
int dj[] = { 1,-1,0,0 };
int n, m;
int lab[10][10];
int copylab[10][10];
vector<p> v;
void dfs(int r, int c) {
    for (int i = 0; i < 4; i++) {
        int nextr = r + di[i];
        int nextc = c + dj[i];
        if (nextr >= 0 || nextr < n || nextc >= 0 || nextc < m) {
            if (copylab[nextr][nextc] == 0) {
                copylab[nextr][nextc] = 2;
                dfs(nextr, nextc);
            }
        }
    }
}
int main() {
    scanf("%d %d", n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", lab[i][j]);
            copylab[i][j] = lab[i][j];
            if (!lab[i][j]) v.push_back({ i,j });
        }
    }
    int Max = 0;
    for (int i = 0; i < v.size() - 2; i++) {
        for (int j = i + 1; j < v.size() - 1; j++) {
            for (int k = j + 1; k < v.size(); k++) {
                p one = v[i];
                p two = v[j];
                p three = v[k];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        copylab[i][j] = lab[i][j];
                    }
                }
                copylab[one.first][one.second] = 1;
                copylab[two.first][two.second] = 1;
                copylab[three.first][three.second] = 1;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (copylab[i][j] == 2)
                            dfs(i, j);
                    }
                }
                int cnt = 0;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (copylab[i][j] == 0)
                            cnt++;
                    }
                }
                Max = max(Max, cnt);
            }
        }
    }
    printf("%d", Max);
    return 0;
}