백준[14502] - 연구소

문제

백준 14502 문제 보기

접근 방법

먼저 벽을 dfs을 활용해 세운 뒤, bfs로 바이러스를 전파시켜 안전 구역을 확인한다. bfs를 한 뒤 이전 맵 상태를 되돌려와야 한다는 것을 주의한다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int N, M, ans = 0;
int temp[9][9];
int map[9][9];
int dr[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};
vector<pair<int, int>> v;
queue<pair<int, int>> q;
int map_copy() {
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
temp[i][j] = map[i][j];
}
}
return 0;
}
int map_recover() {
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
map[i][j] = temp[i][j];
}
}
return 0;
}
int virus_count() {
int cnt = 0;
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
if(map[i][j] == 0){
cnt ++;
}
}
}
ans = max(ans, cnt);
return 0;
}
int dfs(int cnt) {
if(cnt == 3) {
map_copy();
for(int a = 0; a < v.size(); a ++) {
q.push(v[a]);
}
while(!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
for(int x = 0; x < 4; x ++) {
int nextR = r + dr[x];
int nextC = c + dc[x];
if(map[nextR][nextC] == 0 && nextR >= 0 && nextR < N && nextC >= 0 && nextC < M) {
map[nextR][nextC] = 2;
q.push(make_pair(nextR, nextC));
}
}
}
virus_count();
map_recover();
return 0;
}
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
if(map[i][j] == 0) {
map[i][j] = 1;
dfs(cnt + 1);
map[i][j] = 0;
}
}
}
return 0;
}
int main() {
cin >> N >> M;
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
cin >> map[i][j];
if(map[i][j] == 2) {
v.push_back(make_pair(i, j));
}
}
}
for(int i = 0; i < N; i ++) {
for(int j = 0; j< M; j ++) {
if(map[i][j] == 0) {
map[i][j] = 1;
dfs(1);
map[i][j] = 0;
}
}
}
cout << ans;
return 0;
}
Share