[백준 17142] 연구소 3 (C++)

문제 링크: www.acmicpc.net/problem/17142

17142번: 연구소 3

1. 주의할 점

- BFS 수행 도중, 0이 남아있지 않다면 BFS를 종료해도 된다

- 0이 없거나 극단적인 경우(Edge case)도 고려한다

TC #1

4 1
2 2 2 0
2 2 2 2
2 2 2 2
0 2 2 2

 

AC: 3

2. 구현

- 연구소에 대한 정보를 Arr[][]에 담고, 0의 개수를 Zero에 저장한다

- 바이러스의 좌표를 Virus 벡터에 담는다

- V 벡터를 통해 next_permutation을 수행하여 K개의 바이러스만 활성화 되도록 한다 → 큐에 넣는다

- BFS() 함수를 통해 바이러스를 퍼트리며 큐의 크기만큼 퍼졌다면 Zero의 개수를 확인하여 0이라면 BFS를 종료해도 된다

- Zero가 0이 아닌 경우: 연구소 전체에 퍼지지 못한 경우이므로 MAX를 Return하고 이외의 경우는 CheckAll() 함수를 통해 바이러스가 없는 지점까지 퍼지는 걸린 최대 시간을 구하여 반환한다

- 모든 경우에 바이러스가 연구소에 다 퍼지지 못했다면 -1을 출력하고, 이외의 경우는 Result를 출력한다

#define MAX 2501
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int y,x;
};
info tmp;
vector<info> virus;
vector<int> v;
int num,k,len,result,zero;
int arr[50][50];
int check[50][50];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

int checkAll(){
    int cnt=0;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            if(arr[i][j]==1 || arr[i][j]==2) continue;
            if(check[i][j]==MAX)    return MAX;
            cnt = max(cnt, check[i][j]);
        }
    return cnt;
}

int bfs(){
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            check[i][j]=MAX;
    queue<info> q;
    for(int i=0;i<len;i++){
        if(v[i]==1){
            tmp.x = virus[i].x;
            tmp.y = virus[i].y;
            check[tmp.y][tmp.x]=0;
            q.push(tmp);
        }
    }
    int tz = zero;
    while(!q.empty()){
        int qs = q.size();
        for(int k=0;k<qs;k++){
            int cx = q.front().x;
            int cy = q.front().y;
            int cv = check[cy][cx];
            q.pop();
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx]!=1 && check[ny][nx]>cv+1){
                    check[ny][nx]=cv+1;
                    q.push({ny,nx});
                    if(arr[ny][nx]==0) tz--;
                }
            }
        }
        if(tz==0) break;
    }
    if(tz) return MAX;
    else return checkAll();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>num>>k;
    zero=0;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            cin>>arr[i][j];
            if(arr[i][j]==2) virus.push_back({i,j});
            else if(arr[i][j]==0) zero++;
        }
    //초기화
    result = MAX;
    len = virus.size();
    for(int i=0;i<len-k;i++)
        v.push_back(0);
    for(int i=0;i<k;i++)
        v.push_back(1);
    do{
        int temp = bfs();
        if(temp==MAX) continue;
        else result = min(result,temp);
    }while(next_permutation(v.begin(),v.end()));
    
    result==MAX ? cout<<-1 : cout<<result;
    return 0;
}