[백준 17142] 연구소3

1. 전부 입력받는다 (바이러스는 기본적으로 비활성화 시킨 상태로 저장)

2. 입력받은 바이러스 중 m개의 바이러스를 뽑는다.

3. 다 뽑았으면 바이러스를 새로운 지도에 퍼뜨려본다.

4. 새로운 지도에 바이러스가 다 퍼질 때까지의 최소시간을 구한다.

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
#define endl "\n"
#define space " "
#define MAX 99999999
 
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
struct data{int y,x;};
queue<struct data> q;
vector<pair<int,int>> virus; // 모든 바이러스
vector<pair<int,int>> virus_pos; // 뽑은 바이러스 
 
int arr[52][52]; // 입력받은 지도
int map[52][52]; // 바이러스 퍼뜨릴 지도
bool visited[12]; // 바이러스 뽑는 용도
 
int n,m,x,y,ans=MAX,temp,cnt;
 
void copy_map(){
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            map[i][j]=arr[i][j];
}
 
int spread(){
    temp=0;
    while(!q.empty()){
        y=q.front().y;
        x=q.front().x;
        q.pop();
        
        for(int k=0; k<4; k++){
            int nx=x+dx[k];
            int ny=y+dy[k];
            
            if(0<=nx && nx<n && 0<=ny && ny<n){
                if(arr[ny][nx]==0 && map[ny][nx]==0){
                    q.push({ny,nx});
                    map[ny][nx]=map[y][x]+1;
                }
                // 비활성화 바이러스라도 일단 퍼뜨려보자
                if(arr[ny][nx]==-2 && map[ny][nx]==-2){
                    q.push({ny,nx});
                    map[ny][nx]=map[y][x]+1;
                }
            }
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << map[i][j] << space ;
            // 아직 빈공간이면 틀린거임
            if(map[i][j]==0){
                return MAX;
            }
            // 처음 입력 받아을 때 빈공간이었던 자리 중에서 최소시간 
            else if(temp<map[i][j] && arr[i][j]==0)
                temp=map[i][j];
        }
    }
    return temp;
}
 
void func(int cur, int cnt){
    if(cnt==m){
        copy_map(); // 지도 복사
 
        // m개만큼 뽑은 바이러스를 큐에 넣기
        for(int i=0; i<virus_pos.size(); i++){
            map[virus_pos[i].first][virus_pos[i].second]=1;
            q.push({virus_pos[i].first, virus_pos[i].second});
        }
 
        // 큐에 넣은 후에 최소시간 고르기
        cnt=spread();
        ans=min(ans,cnt);
        return;
    }
    
    // 바이러스 고르기
    for(int i=cur; i<virus.size(); i++){
        if(!visited[i]){
            visited[i]=true;
            virus_pos.push_back(make_pair(virus[i].first, virus[i].second));
            func(i+1,cnt+1);
            visited[i]=false;
            virus_pos.pop_back();
        }
    }
}
 
int main(void){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
            
            if(arr[i][j]==2){
                virus.push_back(make_pair(i,j));
                arr[i][j]=-2; // 기본적으로 바이러스 비활성화
            } else if(arr[i][j]==1)
                arr[i][j]=-1; // 벽
        }
    }
    func(0,0);
    
    if (ans==MAX) cout << "-1";
    else if (ans==0) cout << "0";
    else cout << ans-1;
 
    return 0;
}