[BOJ] 17142 : 연구소 3

문제 링크

17142번: 연구소 3 (acmicpc.net)

17142번: 연구소 3

 연구소 모든 칸에 바이러스를 퍼트리는데 걸리는 시간을 구하는 BFS 문제.

풀이

 연구실을 N X N 크기의 칸으로 표현했을 때 각 칸은 0 빈 칸, 1 벽, 2 바이러스 중에 하나로 채워진다.

 바이러스에는 활성 바이러스와 비활성 바이러스가 있다. 둘다 바이러스지만 활성 바이러스는 전염성을 가지고 비활성 바이러스는 전염성이 없다. 하지만 활성 바이러스가 비활성 바이러스와 만나면 활성화시킬 수 있다.

 2 ~ 10개 사이의 바이러스 중에 활성 바이러스는 M개 가 존재한다.

 바이러스들 중에 어떤 M개의 바이러스를 활성 바이러스로 만들어야 가장 빠른 시간내에 연구소를 바이러스로 가득 채울 수 있을 지 구하는 문제다.

 여기서 어떻게 M개를 선택해야지 빠르게 전염시키는데 유리할지는 구하는 방법이 없다. 따라서 모든 경우의 수를 다 해보아야한다.

 나는 백트래킹을 이용해서 선택한 활성 바이러스가 M개가 되면 BFS를 이용해서 모든 칸에 바이러스를 퍼트릴 수 있는지, 가능하다면 시간이 얼마나 걸리는 지 체크해서 최단시간을 찾았다.

for (int i = idx; i < virus.size(); i++) {
		active_virus.push_back(virus[i]);
		backtracking(depth + 1, i + 1);
		active_virus.pop_back();
}

 active_virus는 활성화 시킬 바이러스의 좌표를 모아놓은 벡터이다. 이 벡터의 크기가 M이 되면 M개를 선택했다는 뜻이다. 위의 코드로 M개의 바이러스를 선택할 수 있다.

M개를 모두 선택했다면 이제 BFS로 탐색을 시작해야한다. BFS로 이동할 수 있는 칸은 벽이 아닌 칸들 중 이전에 방문하지 않았던 칸들로 이동할 수 있으며 범위를 벗어나면 안된다.

Q. 모든 칸에 바이러스가 퍼졌는지는 어떻게 체크할까?

A. 초기 입력시에 빈 칸의 수 즉 0의 개수를 저장해두고, 탐색하면서 빈 칸에 바이러스를 퍼트리게되면 이 개수를 하나씩 줄여나간다. 만약 남은 빈 칸의 수가 없으면 모든 칸에 바이러스가 퍼졌다는 뜻이므로, 이때까지 걸린 시간을 체크해서 최소시간을 찾는다.

 처음에는 위 방법대로 하지않아서 문제가 발생했었다. 처음엔 방문되지않은 비활성 바이러스를 만나면 이 바이러스를 활성시키는 것으로 했다.

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1

그렇게 하게 되면 마지막 예제에서 이미 모든 칸이 빈 칸 없이 바이러스로 채워졌는다. 하지만 비활성 바이러스를 만나면 활성화 시키므로 이때의 시간이 계산된다. 그래서 4라는 값을 출력하고 있었다.

그렇다고 비활성 바이러스를 만났을 때 더 이상 탐색을 하지 않는다면?

5 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 2 0 2 0
1 1 1 1 1

 위의 반례(질문검색에서 찾았습니다)에서 두 바이러스 중 하나를 활성화 시켰을 때 다른 바이러스를 만나면 탐색을 종료한다. 그럼 모든 칸에 바이러스를 퍼트리지 못하게된다.

그래서 생각해낸 방법이 빈 칸의 수를 저장해서 모든 칸이 바이러스로 가득찼는지 확인하는 방법이었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 50 + 5;
int lab[MAX_N][MAX_N];
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int N, M;
vector<pair<int, int>> virus;
vector<pair<int, int>> active_virus;
bool visited[MAX_N][MAX_N];
int ans = INF;
int Blank;
 
void backtracking(int depth, int idx);
bool is_ok(pair<int, int> position);
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int blank = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> lab[i][j];
            if (lab[i][j] == 2)
                virus.push_back({ i,j });
            else if (!lab[i][j])
                Blank++;
        }
    }
    backtracking(0, 0);
    if (ans == INF)
        cout << "-1\n";
    else cout << ans << "\n";
    return 0;
}
 
void backtracking(int depth, int idx) {
    if (depth == M) {
        //bfs 시작
        queue<pair<pair<int, int>, int>> q;
        for (int i = 0; i < active_virus.size(); i++)
            q.push({ active_virus[i], 0 });
        int Max_time = -1;
        int remain_blank = Blank;
        if (!remain_blank) {
            ans = 0;
            return;
        }
        memset(visited, 0, sizeof(visited));
        while (!q.empty()) {
            pair<int, int> now = q.front().first;
            int Time = q.front().second;
            q.pop();
            if (visited[now.first][now.second])
                continue;
            visited[now.first][now.second] = true;
            if (lab[now.first][now.second] == 0)
                remain_blank--;
            Max_time = max(Max_time, Time);
            if (!remain_blank) {
                ans = min(ans, Max_time);
                return;
            }
            for (int i = 0; i < 4; i++) {
                pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
                if (!is_ok(next))
                    continue;
                q.push({ next, Time + 1 });
            }
        }
        return;
    }
    else {
        for (int i = idx; i < virus.size(); i++) {
            active_virus.push_back(virus[i]);
            backtracking(depth + 1, i + 1);
            active_virus.pop_back();
        }
    }
}
 
bool is_ok(pair<int, int> position) {
    if (position.first < 0 || position.first >= N || position.second < 0 || position.second >= N
        || visited[position.first][position.second] || lab[position.first][position.second] == 1)
        return false;
    return true;
}