[백준] 17142 - 연구소 3

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

17142번: 연구소 3

 

시간 제한이 짧은 문제인만큼 시간 단축을 위한 아이디어를 떠올리는 것이 중요하다.

 

핵심 아이디어는 각각의 바이러스가 서로의 전파를 방해하지 않기 때문에, 각 바이러스를 전파 시킨 후에 가장 먼저 전파된 시간을 선택하면 된다는 것.

 

우선, 각각의 바이러스를 활성시키고 이를 전파한 결과를 기록한다.

여러 개의 바이러스를 활성화 시키는 경우 앞서 전파한 시간을 가져온 뒤, 해당 위치에서 최솟값을 선택하면 된다.

모든 위치의 전파 시간 중 최댓값을 고르면, 그 값이 최종 전파 시간이 된다.

 

이를 모든 상황에 대해 탐색하여 최솟값을 계산하면 된다.

 

<C++ 코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int dfs(int pol[][50][50], int n, int m, int v, int depth, int len, int sel[]){
    if(len == m){
        int r = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int tmp = 10000;
                for(int k=0; k<m; k++){
                    if(pol[sel[k]][i][j] != 0)
                        tmp = min(tmp, pol[sel[k]][i][j]);
                }
                r = max(r, tmp);
            }
        }
        return r;
    }
    if(depth == v){
        return 10000;
    }
 
    int a = dfs(pol, n, m, v, depth+1, len, sel);
    sel[len] = depth;
    int b = dfs(pol, n, m, v, depth+1, len+1, sel);
    return min(a, b);
}
 
int main(){
    int n, m;
    int lab[50][50] = {};
    int pol[10][50][50] = {};
    int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
    vector<pair<int, int> > vir;
    scanf("%d %d", &n, &m);
 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &lab[i][j]);
            if(lab[i][j] == 2){
                vir.push_back(make_pair(i, j));
            }
        }
    }
 
    // 벽 표기
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(lab[i][j] != 0){
                for(int v=0; v<vir.size(); v++){
                    pol[v][i][j] = -1;
                }
            }
        }
    }
 
    // 바이러스 미리 전파
    for(int v=0; v<vir.size(); v++){
        queue<pair<int, pair<int, int> > > q;
        bool vis[50][50] = {};
        q.push(make_pair(0, make_pair(vir[v].first, vir[v].second)));
        vis[vir[v].first][vir[v].second] = true;
        while(!q.empty()){
            int t = q.front().first;
            int y = q.front().second.first, x = q.front().second.second;
            q.pop();
            for(int d=0; d<4; d++){
                int ay = y + dy[d], ax = x + dx[d];
                if(ay >= 0 && ax >= 0 && ay < n && ax < n && lab[ay][ax] != 1 && !vis[ay][ax]){
                    if (pol[v][ay][ax] != -1)  
                        pol[v][ay][ax] = t + 1;
                    vis[ay][ax] = true;
                    q.push(make_pair(t + 1, make_pair(ay, ax)));
                }
            }
        }
    }
 
    // m 개 선택 후, 계산
    int sel[10] = {};
    int re = dfs(pol, n, m, vir.size(), 0, 0, sel);
    if(re == 10000)
        printf("-1");
    else
        printf("%d", re);
 
    return 0;
}