14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
안전 영역의 크기를 구하는 공식을 잘못 구했다. 빈칸의 개수에서 추가된 벽의 개수(3)와 확산된 바이러스의 개수를 빼면 안 된다. DFS에서 거쳐간 모든 바이러스의 개수가 빠지고, 확산되기 전 바이러스도 포함된다. 따라서 벽이 아닌 칸의 개수(빈칸의 개수 + 확산되기 전 바이러스의 개수)에서 추가된 벽의 개수와 바이러스의 개수를 빼야 한다.
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int lab[8][8], vst[8][8], vstn;
vector<pair<int, int>> blk, vir;
vector<int> sel;
int rem, ans;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void DFS(int r, int c) {
vst[r][c] = vstn;
--rem;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || N <= nr || nc < 0 || M <= nc || vst[nr][nc] == vstn || lab[nr][nc] == 1) {
continue;
}
DFS(nr, nc);
}
}
void wall(bool b) {
for (auto s : sel) {
lab[blk[s].first][blk[s].second] = b;
}
}
void BF(int i) {
if (sel.size() == 3) {
wall(1);
rem = blk.size() + vir.size() - 3;
++vstn;
for (auto v : vir) {
if (vst[v.first][v.second] != vstn) {
DFS(v.first, v.second);
}
}
if (rem >= ans) {
ans = rem;
}
wall(0);
return;
}
for (; i < blk.size(); ++i) {
sel.push_back(i);
BF(i + 1);
sel.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < M; ++c) {
cin >> lab[r][c];
if (lab[r][c] == 0) {
blk.emplace_back(r, c);
}
else if (lab[r][c] == 2) {
vir.emplace_back(r, c);
}
}
}
BF(0);
cout << ans;
return 0;
}