[백준] 17142 연구소 (C++)

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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 *

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

---

풀이

모든 경우의 수를 조사해보며 바이러스가 모두 퍼지는 시간을 구하여 최소 시간을 구해야 하는 문제이다.

연구소의 크기가 최대 50×50 이고 활성화할 수 있는 바이러스의 수는 최대 10이므로 브루트포스가 충분히 가능하다.

바이러스를 활성화하는 경우의 수를 고르는 것과 퍼지는 시간을 구하는 것을 따로 구분한다면 쉽게 문제를 풀 수 있다.

 

바이러스를 활성화하는 경우의 수를 고르는 것은 백트래킹을 활용하여 쉽게 구현할 수 있고

바이러스가 퍼지는 데 걸리는 시간을 구하는 것은 BFS를 활용하여 쉽게 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, numViruses, numAreas;
int answer = 5000;
int graph[51][51];
bool visited[51][51];
vector<pair<int, int>> viruses;
int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

void solve(vector<int> selected);

// 방문 처리
void resetVisited(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            visited[i][j] = false;
        }
    }
}

// 백트래킹으로 바이러스를 활성화할 수 있는 모든 경우의 수 조사
void backTracking(int idx, vector<int> selected){
    if (selected.size() == m){
        solve(selected);
        return;
    }
    for (int i = idx; i < numViruses; i++){
        selected.push_back(i);
        backTracking(i+1, selected);
        selected.pop_back();
    }
}

// BFS로 바이러스가 퍼지는 데 걸리는 시간 조사
void solve(vector<int> selected){
    resetVisited();
    queue<pair<int, int>> que;
    int cnt = numViruses;
    int date = 0;

    for (int i = 0; i < m; i++){
        que.push(viruses[selected[i]]);
        visited[viruses[selected[i]].first][viruses[selected[i]].second] = true;
    }

    while (!que.empty() && cnt < numAreas){
        date++;
        int size = que.size();
        for (int i = 0; i < size; i++){
            int curY = que.front().first;
            int curX = que.front().second;
            que.pop();

            for (int j = 0; j < 4; j++){
                int nextY = curY + direction[j][0];
                int nextX = curX + direction[j][1];
                if (nextY < 1 || nextY > n || nextX < 1 || nextX > n 
                || visited[nextY][nextX] || graph[nextY][nextX] == 1){
                    continue;
                }
                if (graph[nextY][nextX] == 0){
                    cnt++;
                }
                que.push({nextY, nextX});
                visited[nextY][nextX] = true;
            }
        }
    }
    // 모든 영역을 채우기 전에 while문을 탈출하였다면 반영 X
    if (cnt == numAreas){
        answer = min(answer, date);
    }
}

int main(){
    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> graph[i][j];
            if (graph[i][j] == 2){
                viruses.push_back({i, j});
                numViruses++;
                numAreas++;
            }
            else if (graph[i][j] == 0){
                numAreas++;
            }
        }
    }

    backTracking(0, {});
    if (answer == 5000){
        cout << -1;
    }
    else{
        cout << answer;
    }
}