[BOJ][삼성기출] 17142. 연구소3

문제

연구소3

문제 접근

완전탐색+BFS 문제이다.

관건1. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

BFS는 M개의 바이러스를 선택한 뒤 실행된다.
여기서 선택하는 M개의 바이러스란 유일하게 활성 상태인 바이러스의 개수가 아니라, 복제를 시작하는 바이러스를 의미한다.
(즉, 최초에 선택되지 못해 비활성 상태인 바이러스도 나중에 활성 상태가 될 수 있다.)

따라서 BFS에서 큐에 원소를 넣는 조건이 중요하다.
(처음에 단순히 빈 공간일 경우만 큐에 넣도록 해서 틀렸다.)

1차 시도: 빈칸과 비활성 바이러스를 모두 큐에 넣음.

이 경우, 비활성 바이러스가 연속으로 있을 경우 비활성 바이러스를 탐색하는 시간이 계산되어버림.
큐에서 매번 원소를 꺼낼 때마다 맵 전체를 순회하며 종료 조건을 탐색하게 했음(시간 초과.)

2차 시도: 종료 조건 재구성

입력으로 주어지는 맵에서 빈 공간의 수를 센다.
큐에서 빠져나오는 원소가 빈 공간을 의미하는 원소일 경우만 따로 카운팅해서 빈 공간이 모두 방문된 경우 수행을 종료하도록 했다.

비활성 바이러스가 활성 바이러스가 될 수 있는 경우를 생각하지 못하다 반례를 보고 찾았다. 문제를 더 꼼꼼하게 분석할 것,,
종료 조건 (빈 공간이 모두 탐색)을 확인할 때 굳이 맵을 traverse할 필요가 없다! 개수로 확인하는 방법을 적절히 활용할 필요가 있다.

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;

typedef struct node {
    int x;
    int y;
    int active;
} node;

vector<node> Nodes;
int N, M, rst, E = 0;
int map[50][50];
int is_visit[50][50];
bool is_fail;
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 };

void input() {
    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){
                node tmp;
                tmp.x = i; tmp.y = j; tmp.active = 0;
                Nodes.push_back(tmp);
            }
            if (map[i][j] == 0) E++;
            
        }
    }
    rst = INT_MAX;
    is_fail = true;
}

int is_range(int x, int y) {
    if (x >= 0 && x < N && y >= 0 && y < N) return true;
    return false;
}

int spread() {
    queue< pair< pair<int, int>, int> > Q;
    memset(is_visit, 0, sizeof(is_visit));
    
    for (int i = 0; i < Nodes.size(); i++) {
        if (Nodes[i].active) {
            is_visit[Nodes[i].x][Nodes[i].y] = 1;
            Q.push(make_pair(make_pair(Nodes[i].x, Nodes[i].y), 0));
        }
    }
    int empty = E;
    int time = 0;
    while (!Q.empty()) {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int t = Q.front().second;
        
        time = max(time, t);
        if (map[x][y] == 0) {
            empty--;
            if(empty == 0) return time;
        }
        Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (is_range(nx, ny) && map[nx][ny] != 1 && !is_visit[nx][ny]) {
                is_visit[nx][ny] = t + 1;
                Q.push(make_pair(make_pair(nx, ny), t + 1));
            }
        }
        
    }
    return -1;
    
}

void dfs(int num, int cnt) {
    if (cnt == M) {
        int time = spread();
        if (time != -1) { // 바이러스를 놓아서 확산을 성공할 수 있는 경우가 단 하나라도 있다면, 그게 최소 시간임
            is_fail = false;
            rst = min(rst, time);
        }
        return;
    }
    for (int i = num + 1; i < Nodes.size(); i++) {
        Nodes[i].active = 1;
        dfs(i, cnt + 1);
        Nodes[i].active = 0;
    }
}

void solve() {
    if(E == 0){
        rst = 0;
        return;
    }
    for (int i = 0; i < Nodes.size(); i++) {
        Nodes[i].active = 1;
        dfs(i, 1);
        Nodes[i].active = 0;
    }
    if (is_fail) {
        rst = -1;
    }
}

int main() {
    input();
    solve();
    cout << rst << endl;
}