[17142번] 연구소 3

17142번: 연구소 3

 

www.acmicpc.net

조합  + 탐색 문제

재귀를 통해서 활성시킬 바이러스를 선택 후 BFS를 통해 바이러스를 확산시켜 된다.

 
#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int map[50][50], visit[50][50], arr[50][50];
int drc[] = { 0,0,-1,1,-1,1,0,0 };
int N, M, safeArea, ans = 1e9;
struct pnt { int r, c; };
vector<pnt>virus;
queue<pnt>Q;
bool sel[10];
 
bool chk(int r, int c) {
    if (!(r < 0 || c < 0 || r >= N || c >= N)) return true;
    return false;
}
void bfs() {
    int tmp = 0;
    int area = safeArea;
    while (!Q.empty()) {
        int r = Q.front().r;
        int c = Q.front().c;
        Q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + drc[d];
            int nc = c + drc[d + 4];
            if (chk(nr, nc) && map[nr][nc] != 1 && visit[nr][nc] == -1) {
                visit[nr][nc] = visit[r][c] + 1;
                Q.push({ nr,nc });
                if (map[nr][nc] == 0) {
                    tmp = max(tmp, visit[nr][nc]);
                    area--;
                }
                if (area == 0) break;
            }
        }
    }
 
    if(area == 0)
        ans = min(tmp, ans);
}
 
void selvirus(int cnt,int idx) {
    if (cnt == M) {
        memset(visit, -1, sizeof(visit));
        for (int i = 0; i < virus.size(); i++) {
            int r = virus[i].r;
            int c = virus[i].c;
            if (sel[i] == true) {
                Q.push({ r,c });
                visit[r][c] = 0;
            }
        }
        bfs();
        return;
    }
    for (int i = idx; i < virus.size(); i++) {
        if (sel[i] == true) continue;
        sel[i] = true;
        selvirus(cnt + 1, i + 1);
        sel[i] = false;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> map[r][c];
            if (map[r][c] == 0) 
                safeArea++;
            else if (map[r][c] == 2) 
                virus.push_back({ r,c });
        }
    }
    selvirus(0, 0);
    if (ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}