BOJ 17141 - 연구소 2

www.acmicpc.net/problem/17141

17141번: 연구소 2

 

BFS 와 조합을 써야 풀 수 있는 문제이다.

전체 바이러스의 갯수를 센뒤에 각 바이러스의 좌표를 벡터에 담아둔다

그리고 조합을 사용해서 전체 바이러스의 갯수 중 m 개를 뽑아서 bfs 를 진행한다.

 

* 주의할점은 뽑아놓은 m 개의 바이러스가 동시에 bfs 를 수행해야 한다는 점이다.

이렇게 하기 위해서는 bfs 함수에 들어갈때 바이러스의 좌표 (y, x) 를 큐에 넣는게 아니라,

m 개를 뽑으면서 bfs 함수에서 사용할 큐에 넣어두고 나서 bfs 함수를 수행해야 한다는 점이다.

 

* 또한, bfs 를 통해서 각 바이러스가 퍼지는 시간을 측정해야 하는데,

기존의 입력으로 주어지는 배열로는 시간계산이 어렵기 때문에 

복사본을 만들때, 기존 배열의 빈 칸과 바이러스 부분은 모두 -1 로 잡아두고 벽은 -2 로 잡아둬서

m 개의 바이러스를 뽑을때 해당 바이러스의 좌표들만 0으로 만들고 

bfs 함수를 수행할때마다 하나씩 더하면서 진행하면 정상적으로 수행된다.

 

* 또 하나 주의할 점은, 모든 케이스를 다 돌렸음에도, 바이러스를 모든 빈칸에 채워넣지 못하는경우,

-1을 리턴하도록 해야하는데, 단순히 bfs 를 수행한 이후, 계산된 행렬 내에서 최대값, 최소값을 찾으려하면

올바르지 못한 값이 나올 수 있다

(예제입력 5의 경우 단순히 최대값으로 계산하면 7 이 아니라 10이 나온다)

그래서 각 케이스 별로 계산된 행렬의 결과값을 담는 벡터를 생성해서, -1 이 아닌게 하나라도 있다면

바이러스를 전부 퍼트릴수 있는 케이스가 존재한다는 뜻이므로, -1 을 제외한 값 중 가장 작은 값을 찾아내면 답이되고,

그렇지 못하고 전부 -1 이라면 단 한가지의 경우도 바이러스를 전부 퍼트릴수 있는 케이스가 없다는 소리이므로 -1을 답으로 잡는다.

 

- c++

 

#include <bits/stdc++.h>
 
#define MAX 50
#define INF 987654321
 
using namespace std;
 
int n, m, cnt_virus, answer = INF;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int adj[MAX][MAX], copy_adj[MAX][MAX];
bool visited[MAX][MAX];
bool selected_virus[MAX * MAX];
vector<pair<int, int>> virus;
queue<pair<int, int>> q;
vector<int> vec;
 
int cnt_max_time() {
    int cnt = -1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (copy_adj[i][j] == -1) return -1;
            cnt = max(cnt, copy_adj[i][j]);
        }
    }
    return cnt;
}
 
void copy_map() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (adj[i][j] == 0 || adj[i][j] == 2) copy_adj[i][j] = -1;
            if (adj[i][j] == 1) copy_adj[i][j] = -2;
        }
    }
}
 
void bfs() {
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        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 >= n) continue;
            if (!visited[ny][nx] && copy_adj[ny][nx] == -1) {
                visited[ny][nx] = true;
                q.push(make_pair(ny, nx));
                copy_adj[ny][nx] = copy_adj[y][x] + 1;
            }
        }
    }
}
 
void spread_virus() {
    q.empty();
    copy_map();
    memset(visited, false, sizeof(visited));
    
    int cnt = 0;
    for (int i = 0; i < cnt_virus; ++i) {
        if (cnt == m) break;
        if (selected_virus[i]) {
            int y = virus[i].first;
            int x = virus[i].second;
            q.push(make_pair(y, x));
            copy_adj[y][x] = 0;
            cnt++;
        }
    }
    
    bfs();
    
    int num = cnt_max_time();
    vec.push_back(num);
}
 
void recursion(int idx, int depth) {
    if (depth == m) {
        spread_virus();
        return;
    }
    
    for (int i = idx; i < cnt_virus; ++i) {
        if (selected_virus[i]) continue;
        selected_virus[i] = true;
        recursion(i, depth + 1);
        selected_virus[i] = false;
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> adj[i][j];
            if (adj[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
    
    cnt_virus = virus.size();
    
    recursion(0, 0);
    
    bool flag = false;
    for (int i = 0; i < vec.size(); ++i) 
        if (vec[i] != -1) flag = true;
        
    if (flag) {
        for (int i = 0; i < vec.size(); ++i)
            if (vec[i] != -1) 
                answer = min(answer, vec[i]);
        cout << answer << "\n";
    } else {
        cout << -1 << "\n";
    }
    
    return 0;
}