본문 바로가기

code/BOJ

백준 14502 연구소

 

 

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;
}