연구소 3

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<algorithm>

using namespace std;

vector<pair<int, int>> virus;
int n, m;
int map[50][50];
int posi[50][50];
bool temp[50][50];
bool temp2[50][50];
int ans = 10000000;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] == 2){
                virus.push_back({i,j});
            }
            if(map[i][j] == 1){
                temp[i][j] = true;
                temp2[i][j] = true;
            }
        }
    }
    vector<int> v;
    for(int i = 0; i < virus.size(); i++){
        if(i < m) v.push_back(1);
        else v.push_back(0);
    }
    do{
        queue<pair<int, int>> q;
        memset(posi,0,sizeof(posi));
        memcpy(temp , temp2, sizeof(temp));

        for(int i = 0; i < v.size(); i++){
            if(v[i] == 1){
                q.push({virus[i].first, virus[i].second});
                temp[virus[i].first][virus[i].second] = true;
            }
        }

        while(!q.empty()){
            int x = q.front().first; int y = q.front().second;
            q.pop();
            for(int i = 0; i <4; i++){
                int nx = x + dx[i]; int ny = y+dy[i];
                if(nx>=0 && nx < n && ny >= 0 && ny < n){
                    if(temp[nx][ny] == false){
                            posi[nx][ny] = posi[x][y] + 1;
                            temp[nx][ny] = true;
                            q.push({nx, ny});

                    }
                }
            }
        }
        int max = 0;
        bool go = false;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){

                if(posi[i][j] > max && map[i][j] != 2) max = posi[i][j];
                if(map[i][j] == 0 && posi[i][j] == 0) go = true;

            }
        }
        if(go == false)
        ans = ans > max ? max:ans;

    }while(prev_permutation(v.begin(), v.end()));
    if(ans == 10000000)
        printf("%d\n", -1);
    else printf("%d\n", ans);




}

 

일단 경우의수가 굉장히 작음 , 그 근거는, 바이러스 개수가 10개 제한이며, 이때 10개중에 몇개선택하는건데 5개 선택한다 쳐도 그렇게많지않아서 그냥 조합으로 전부다 해보는게 좋다고생각했다. 그리고 지금 main에 한큐로 써놔서 시간이 12ms 정도 걸렸는데, 다하고나서 계속 다시 체크하는동안에 걸리는 시간을 고려한다면, 조건을 초과해 처음 전수검사 이후는 ans 보다 컸을때 안하는방향으로 해나간다면 조금 더 줄일수있지 않을까? 하는생각이든다. 전형적인 BFS문제지만, 생각해볼게 여러가지있다.

 

바이러스가 비활성상태에서, 활성 상태 가 되는 경우에, 시간을 +1 증가시킬것인지 말것인지에 대해 고민을 많이했었고,

일단 시간을 증가시키는 방향으로 진행을했지만, 만약 ans 를 구했을때 최대 오래걸린 시간에 대한것으로는 채택하지 않았다.

 

예제를 보면,  

* 6 

5 6

이런식으로 나와있는 부분이있었는데, 그냥 비활성화 -> 활성화 단계에서는 시간안잡아먹을거라고 예상하고문제를 풀었다.