[BOJ] 17141. 연구소 2

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

17141번: 연구소 2

처음에 입력을 받을 때 바이러스를 놓을 수 있는 칸(값이 2인 칸)을 벡터에 모두 넣어놓는다.

그리고 이 칸들 중 m개를 선택하여 바이러스 퍼트리는 경우를 모두 해보고 최소 시간을 구한다.

 

 

m개를 모두 골라줬다면 골라준 자리에 바이러스를 넣고 퍼뜨린다.

바이러스를 퍼트리기 위해서 bfs를 사용하고 시간을 구하기 위해서 큐 사이즈만큼 단계별로 진행하였다.

그리고 각 큐 사이즈만큼 시작할 때마다 시간을 1씩 증가시켜서 시간을 구할 수 있다.

이렇게 하면 나중에 큐가 비었을 때도 한 번 더 1이 더해지므로 처음에 시간을 -1부터 시작하든지 나중에 1을 빼주던지 하면 된다.

 

 

바이러스를 모두 퍼뜨렸다면 퍼지는데 걸리는 시간을 리턴해주면 되는데,

모든 빈칸에 바이러스를 퍼졌는지 먼저 검사해주어야 한다.

빈칸인데 바이러스가 퍼져있지 않다면 문제 조건에 따라 시간 대신에 -1을 리턴한다.

 

 

그리고 시간의 최솟값을 구하기 위해서 먼저 정답을 저장할 ans에다가 -1을 초기값으로 넣어놓고 ans가 -1인 경우와 -1이 아닌경우를 나눠서 최솟값을 구해줬다.

먼저 -1인 경우에는 ans가 초기값이거나 bfs의 결괏값이 -1인 경우이다. 이때는 그냥 새로 bfs 한 결과를 바로 넣어주면 된다. -1이 아닌 경우에는 bfs의 결과가 -1이 아닌 ans보다 작은 값이 어야 ans값으로 새로 갱신된다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int ans;
int map[50][50];
bool check[50][50];
vector<pair<int,int> > vt;
vector<int> virus;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int bfs() {
    queue<pair<int, int> > q;
    memset(check, false, sizeof(check));
 
    int x, y;
    //선택한 바이러스를 놓을 수 있는 칸에 바이러스를 놓는다.
    for (int i = 0; i < m; i++) {
        x = vt[virus[i]].first;
        y = vt[virus[i]].second;
 
        q.push(make_pair(x,y));
        check[x][y] = true;
    }
 
 
    int time = -1;
    while (!q.empty()) {
 
        int size = q.size();
        time++;
 
        while (size--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
 
                //범위
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                //방문체크
                if (check[nx][ny]) continue;
                //벽인경우
                if (map[nx][ny] == 1) continue;
 
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
 
            }
        }
        
    }
 
    //바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //빈칸인데 바이러스가 퍼져있지 않다
            if (map[i][j] == 0 && !check[i][j]) return -1;
        }
    }
 
    return time;
 
}
 
void select(int index, int cnt) {
    if (cnt == m) {
        int tmp = bfs();
        if (ans == -1) ans = tmp;
        else {
            if (tmp != -1 && ans > tmp) ans = tmp;
        }
 
        return;
    }
    if (index == vt.size()) {
        return;
    }
 
 
    //index번째 바이러스를 놓는 경우
    virus.push_back(index);
    select(index + 1, cnt+1);
    virus.pop_back();
 
    //바이러스를 놓지 않는 경우
    select(index + 1, cnt);
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            //바이러스를 놓을 수 있는 칸이면 벡터에 넣는다.
            if (map[i][j] == 2) vt.push_back(make_pair(i, j));
        }
    }
 
    ans = -1;
 
    select(0, 0);
    
    cout << ans << '\n';
 
 
    return 0;
}