[17142번] 연구소 3

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

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

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 * - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

 이 문제는 올해 상반기 삼성코딩테스트에 출제되었던 문제이다.

 

문제접근법.

1. 바이러스 M개를 선택하는 함수를 정의한다.

2. 바이러스를 큐를 이용한 BFS로 퍼트리면서, 모든 칸에 바이러스가 퍼졌는지 확인한다.

 

 바이러스 M개를 선택하기 위해서, 조합 함수를 정의한다. 조합 함수는 재귀적으로 구성되며, 매개 변수로 특정 순서의 바이러스 번호와 지금까지 총 몇 개의 바이러스를 선택했는지 갯수를 가진다. 재귀적으로 특정 순서의 바이러스를 선택했을 때와 선택하지 않았을 때으로 호출하면 된다.

 

 바이러스가 모두 퍼졌는지 확인하기 위해서, 큐에 행, 열, 시간 정보를 포함한 원소를 삽입한다. 단, 주의할 점은 벽이 아니고 비활성화 바이러스를 만났을 때는 활성화 바이러스가 되어야 한다. 큐에 들어가는 아이템들이 중복이 되지 않기 위해서, 체크 배열을 적절하게 사용한다.

 

 예제들을 모두 푼다면, 쉽게 통과할 수 있는 문제이다.

 

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;
int map[51][51];
int empty_cnt = 0;
int answer = -1;
int op[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
 
typedef struct virus {
    int r;
    int c;
    int time;
    virus(int _r, int _c, int _t) : r(_r), c(_c), time(_t) {};
};
 
vector<virus> b_v;
int arr[11];
 
int spread() {
    int check[51][51];
    memset(check, 0, sizeof(check));
    int time = 0;
    int space = 0;
    queue<virus> q;
 
    for (int i = 0; i < M; i++) {
        q.push(b_v.at(arr[i]));
        check[b_v.at(arr[i]).r][b_v.at(arr[i]).c] = 1;
    }
 
    while (!q.empty()) {
        int r = q.front().r;
        int c = q.front().c;
        time = q.front().time;
        if (answer != -1 && time >= answer)
            break;
 
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int n_r = r + op[i][0];
            int n_c = c + op[i][1];
 
            if (n_r < 1 || n_r > N || n_c < 1 || n_c > N || check[n_r][n_c] == 1 || map[n_r][n_c] == 1)
                continue;
 
            q.push(virus(n_r, n_c, time + 1));
            check[n_r][n_c] = 1;
            if (map[n_r][n_c] == 0) {
                space++;
                if (space == empty_cnt) {
                    return time + 1;
                }
            }
        }
    }
 
    // Exit
    return -1;
}
 
void comb(int idx, int cnt) {
    if (cnt == M) {
        // Spread
        int temp = spread();
        if (temp != -1) {
            if (answer == -1)
                answer = temp;
            else
                answer = min(answer, temp);
        }
        return;
    }
 
    if (idx == b_v.size())
        return;
 
    arr[cnt] = idx;
    comb(idx + 1, cnt + 1);
    comb(idx + 1, cnt);
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
 
    // Input
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {
                b_v.push_back(virus(i, j, 0));
            }
            else if (map[i][j] == 0)
                empty_cnt++;
        }
    }
 
    // Comb
    if (empty_cnt != 0)
        comb(0, 0);
    else
        answer = 0;
 
    cout << answer << endl;
    return 0;
}