백준 14502번 - 연구소

https://www.acmicpc.net/problem/14502

순서대로 벽을 세운 뒤에 벽이 3개가 세워지면

차례로 바이러스가 퍼질 수 있는 곳이 몇개인지 DFS를 통해 풀 수 있도록 했다.

 

안전 영역의 개수가 최대로 나와야하기 때문에 바이러스가 가장 적게 퍼질 때의 값을 구한 뒤에

전체 공간에서 바이러스가 최소로 퍼진 공간과 벽의 개수(새로 새운 3개의 벽까지 추가)를 함께 빼주면

답을 구할 수 있다.

#include <iostream>
#include <vector>
using namespace std;
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
int N,M;
int ans=0; //바이러스가 최소로 퍼졌을 때의 값
int virus_cnt=0; //바이러스가 퍼졌을 때의 값
vector<vector<int>> map;
vector<vector<int>> visited; //방문 유무
void dfs_virus(int y,int x){
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=M)
            continue;
        
        if(map[ny][nx]==1 || visited[ny][nx])
            continue;
        
        visited[ny][nx]++;
        virus_cnt++;
        dfs_virus(ny, nx);
    }
}
void dfs_wall(int cnt){
    
    //안전영역 구하기
    if(cnt==3){
        
        virus_cnt=0;
        visited=vector<vector<int>> (N,vector<int>(M,0));
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==2 && !visited[i][j]){
                    visited[i][j]=1;
                    virus_cnt++;
                    dfs_virus(i,j);
                }
            }
        }
        
        if(ans==0) ans=virus_cnt;
        else    ans=min(ans,virus_cnt);
        
        return;
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0){
                map[i][j]=1;
                dfs_wall(cnt+1);
                map[i][j]=0;
            }
        }
    }
}
int main(){
    
    cin>>N>>M;
    map=vector<vector<int>> (N,vector<int>(M,0));
    int wall_cnt=0;
    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_cnt++;
        }
    }
    
    dfs_wall(0);
    cout<<(N*M)-(wall_cnt+3+ans)<<endl;
    
    return 0;
}