BOJ 17142 - 연구소 3

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

생각보다 이해하는데 시간이 꽤 걸렸던 문제다.

백준 17141 번 연구소 2와 거의 유사하긴 하나, 

선택하지 않은 바이러스(비활성 바이러스) 의 경우, 시간 처리를 +1 을 해주지 않고

그대로 bfs 값을 넘겨 받아야 한다는게 차이점이었다.

 

예를들어, 주어진 맵이 다음과 같다고 하면

N = 4, M = 2

0 1 1 0
2 1 1 2
2 1 1 2
0 1 1 0

 

이 맵에 대한 연구소 3의 코드 실행 결과는 2가 나와야 한다.

만약 (0, 1), (3, 2) 의 바이러스를 활성 바이러스로 선택해서 진행했다면 결과가 이렇게 될 것이다.

1 - - 2

0 - - *

* - - 0

2 - - 1

 

( - 는 벽이고, 0 은 활성화된 바이러스 이며, * 은 선택하지 않은 비활성 바이러스이다, 나머지 숫자는 경과 시간이다)

 

bfs 코드를 진행함에 있어서, * 위치에 실제로 저장된 값은 1이 들어갈 테지만

(그래야, 상하좌우로 움직이는 bfs 에서 2에 해당하는 좌표( (0, 3), (3, 0) )에 접근할 수 있음)  

빈 공간이 아니기때문에, 빈 공간과 비활성 바이러스 * 을 구분하는 별도의 요소를 만들어야 한다.

 

이를 위해서, 초기에 맵에 대한 정보를 입력을 받을 때 빈 공간 (0) 의 갯수를 미리 다 세두고,

bfs 를 수행하면서 0 의 갯수를 센다. 

둘의 갯수가 일치한다면, 바이러스가 모든 빈공간의 좌표에 접근할 수 있다는 뜻이되며,

이 조건을 만족할때, 총 걸린 시간 계산을 수행한다.

그렇지 않다면 모든 빈 공간의 좌표에 접근 하지 못했다는 의미이므로 -1 을 출력해준다. 

 

 

- c++

 

#include <bits/stdc++.h>
 
#define MAX_N 50
#define MAX_M 10
#define INF 1e9
 
using namespace std;
 
int n, m, answer = INF, virus_cnt, empty_cnt;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int adj[MAX_N][MAX_N], copy_adj[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
bool selected_virus[MAX_M];
vector<pair<int, int>> virus;
queue<pair<int, int>> q;
 
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() {
    int total_time = 0, empty_space = 0;
    
    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;
                copy_adj[ny][nx] = copy_adj[y][x] + 1;
                if (adj[ny][nx] == 0) {
                    empty_space++;
                    total_time = copy_adj[ny][nx];                
                }
                q.push(make_pair(ny, nx));
            }
        }
    }
    
    if (empty_cnt == empty_space)
        answer = min(answer, total_time);
}
 
void spread_virus() {
    memset(visited, false, sizeof(visited));
    copy_map();
    
    int cnt = 0;
    for (int i = 0; i < virus_cnt; ++i) {
        if (cnt == m) break;
        if (selected_virus[i]) {
            int y = virus[i].first;
            int x = virus[i].second;
            copy_adj[y][x] = 0; 
            q.push(make_pair(y, x));
            cnt++;
        }
    }
    
    bfs();
}
 
void recursion(int idx, int depth) {
    if (depth == m) {
        spread_virus();
        return;
    }
    
    for (int i = idx; i < virus_cnt; ++i) {
        if (selected_virus[i]) continue;
        selected_virus[i] = true;
        recursion(i + 1, 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] == 0) empty_cnt++;
            if (adj[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
    
    virus_cnt = virus.size();
    
    recursion(0, 0);
    
    if (answer == INF) cout << "-1" << "\n";
    else cout << answer << "\n";
    
    return 0;
}