[백준]연구소2

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

17141번: 연구소 2

연구소 시리즈 문제.. 조합으로 바이러스를 선택하면 된다. 그리고 bfs를 해줌.

전부 탐색이 됐는지 안됐는지 따지기 위해 탐색이 될 수 있는 공간을 구해서 체크해주는 것이 포인트.

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
 
int N, M, space = 0;
int map[50][50], isV[50][50];
bool com[10];
vector<pair<int, int> > birus; //M개 선택
queue <pair<int, int> > q;
int ans = 1e9;
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
 
int bfs() {
    int cnt = 0, time = 0;
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second; q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= N || isV[nr][nc] != -1 || map[nr][nc] == 1) continue;
            
            q.push(make_pair(nr, nc));
            isV[nr][nc] = isV[r][c] + 1;
            time = isV[nr][nc];
            cnt++;
        }
    }
 
    if (cnt == space + birus.size() - M) return time;
    return 1e9;
    //if(cnt == space+ birus.size()-M && ans > time) ans=time //이거로만 해도됨 void형.
}
 
void dfs(int s, int len) {
    if (len == M) {
        memset(isV, -1, sizeof(isV));
        for (int i = 0; i < birus.size(); i++) {
            if (com[i]) { 
                q.push(make_pair(birus[i].first, birus[i].second));
                isV[birus[i].first][birus[i].second] = 0;
            }
        }
        
        int a = bfs();
        if (ans >= a) ans = a;
        return;
    }
 
    for (int i = s; i < birus.size(); i++) {
        if (!com[i]) {
            com[i] = true;
            dfs(i, len + 1);
            com[i] = false;
        }
    }
}
 
int main()
{
    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] == 0) space++;
            if (map[i][j] == 2) birus.push_back(make_pair(i, j));
        }
    }
    
    dfs(0, 0);
    printf("%d\n", ans == 1e9 ? -1 : ans);
    return 0;
}