BOJ 17142 - 연구소3(C++)

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

17142번: 연구소 3

풀이

0. 입력데이터에서 바이러스의 위치, 2번의 완료조건(바이러스가 퍼져야하는 방의 수)를 저장

1. 입력 데이터의 바이러스 중 M개의 바이러스를 활성화  

    - 모든 바이러스중 M개를 선택하여 모든 경우의 수에 대해 시뮬레이션(브루트포스)

2. 활성 상태의 바이러스는 상하좌우로 전파되며 모든 빈칸에 바이러스가 퍼지는 최소 시간을 구함

   - 1에 대한 모든 경우의 수에 bfs를 이용하여 바이러스가 퍼지는 시간을 구함

   - 퍼진 바이러스의 수 == 바이러스가 퍼져야하는 방의수(벽을 제외한 수)의 경우 최소시간을 비교/갱신

3. 모든 칸에 바이러스를 퍼뜨릴수 없는 경우는 -1을 출력

 

#include <cstring>
#include <vector>
#include <iostream>
#include <queue>

#define MAX 987654321
using namespace std;

int N, M;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int map[51][51];
bool visit[51][51];
vector<pair<int, int>> virus_pos;//모든 바이러스의 위치
vector<int> virus;//바이러스 전파시작전 활성화된 바이러스의 인덱스
int MIN = MAX;
int empty_cnt;

struct point {
    int y, x, dis;
};

void spread_virus() {
    memset(visit, false, sizeof(visit));
    queue<point> q;
    int y, x, dis,time=0;
    int virus_cnt = virus_pos.size();//현재 바이러스의 수, 비활성 바이러스도 포함

    for (int i = 0; i < virus.size(); i++) {//활성화한 바이러스를 큐와 visit에 갱신
        y = virus_pos[virus[i]].first;
        x= virus_pos[virus[i]].second;
        visit[y][x] = true;
        q.push(point{ y,x,0 });
    }

    while (!q.empty()) {
        y = q.front().y;
        x = q.front().x;
        dis = q.front().dis;
        q.pop();

        if (virus_cnt == empty_cnt) {//벽을 제외한 모든방에 바이러스가 전파
            if (MIN > time) {
                MIN = time;
            }
            return;
        }

        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            if (ny<1 || nx<1 || ny>N || nx>N)continue;//연구소 사이즈를 벗어나면 pass
            if (visit[ny][nx] || map[ny][nx] == 1)continue;//이미 활성화 되었거나 벽이면 pass
            time=dis+1;
            if(map[ny][nx]==0)//전파된 바이러스의 수
                virus_cnt++;
            visit[ny][nx] = true;
            q.push(point{ ny,nx, dis + 1 });
        }
    }
}

void decide_virus(int idx, int cnt) {
    if (cnt == M) {
        spread_virus();
        return;
    }
    for (int i = idx; i < virus_pos.size(); i++) {
        virus.push_back(i);
        decide_virus(i + 1, cnt + 1);
        virus.pop_back();
    }
}

int main() {
    cin >> N >> M;
    empty_cnt = N * N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) {//바이러스를 놓을 수 있는 위치를 저장
                virus_pos.push_back(make_pair(i, j));
            }
            else if (map[i][j] == 1) empty_cnt--;//bfs종료조건 = 전파되어야하는 바이러스의 수 = 연구소 방의개수-벽의 개수
        }
    }
    decide_virus(0, 0);

    if (MIN == MAX) {
        cout << -1;
    }
    else {
        cout << MIN;
    }
    
    return 0;
}