[백준/구현/C++] 17141번 연구소2

문제는 여기!

#include <bits/stdc++.h>

using namespace std;
int N, M;
int MAP[51][51];
queue<pair<int, int>> virus;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool visited[51][51];
vector<pair<int, int>> virusSite; // 바이러스 놓을 수 있는 자리
int arr[10];
bool isVisited[11];
int answer = 2e9, cntZero = 0;

void clearMap(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            visited[i][j] = false;
        }
    }
    for(int i=0; i<M; i++){
        isVisited[i] = false;
    }
}

void solve() {

    int cnt = cntZero, ans = 0;
    for (int i = 0; i < M; i++) {
        int x = virusSite[arr[i]].first;
        int y = virusSite[arr[i]].second;

        visited[x][y] = true;
        virus.push({x, y});
    }

    while (!virus.empty()) {

        int size = virus.size();
        for(int i=0; i<size; i++){

            int x = virus.front().first;
            int y = virus.front().second;
            virus.pop();

            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (MAP[nx][ny] == 1 || visited[nx][ny]) continue;

                virus.push({nx, ny});
                visited[nx][ny] = true;
                cnt--;
            }
        }
        ans++;
    }
    if(cnt - M == 0) answer = min(answer, ans-1);
}

void makeArr(int start, int cnt) {
    if (cnt == M) {
        clearMap();
        solve();
        return;
    }

    for (int i = start; i < virusSite.size(); i++) {
        if (!isVisited[i]) {
            isVisited[i] = true;
            arr[cnt] = i;
            makeArr(i, cnt + 1);
            isVisited[i] = false;
        }
    }
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int x;
            cin >> x;
            MAP[i][j] = x;
            if (x == 2) virusSite.push_back({i, j});
            if (x != 1) cntZero++;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    makeArr(0, 0);

    if(answer == 2e9) cout << -1;
    else cout << answer;

    return 0;
}