(C++) - 백준(BOJ) 17141번 : 연구소 2

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX 987654321
using namespace std;
//nXn개의 정사각형 중 m개의 바이러스를 방이 2인 곳에 떨군다. 조합 문제!! (2의 개수) C m 꼴
int ck[51][51];
int lab[51][51];
int cop[51][51];
int d[51][51];
int visited[11]; //놓을 수 있는 바이러스의 최대 개수
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
vector <pair<int, int>> p,v;
int n, m, ans = MAX;
 
int BFS() {    //BFS탐색방식으로 바이러스를 퍼뜨린다.
    queue <pair<int, int>> q;
 
    int cnt = 0;
    int tmp = 0;
 
    memset(ck, 0, sizeof(ck));
    memset(d, 0, sizeof(d));
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cop[i][j] = lab[i][j];            //lab에서 카피 한 후 
 
    for (int i = 0; i < v.size(); i++)
    {
        cop[v[i].first][v[i].second] = 3;    //바이러스를 퍼뜨릴 방을 m만큼 정한다.
        ck[v[i].first][v[i].second] = 1;    //체크해주고
        q.push({ v[i].first,v[i].second }); //노드 push
    }
 
    while (!q.empty())
    {
        for (int k = 0; k < q.size(); k++)    //m개만큼의 노드를 순회
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i]; 
                int ny = y + dy[i];
                if (1 <= nx && nx <= n && 1 <= ny && ny <= n)
                {
                    if (cop[nx][ny] != 1 && ck[nx][ny] == 0)
                    {
                        q.push({ nx,ny });
                        ck[nx][ny] = 1;
                        cop[nx][ny] = 3;
                        d[nx][ny] = d[x][y] + 1;
                        cnt = max(cnt, d[nx][ny]); //바이러스 근원지로부터 최대 거리 저장
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++)//최대한 오염시켰으나 빈방이 있을 경우 MAX반환
    {
        for (int j = 1; j <= n; j++)
        {
            if (!cop[i][j])
                return MAX;
        }
    }
    return cnt;
}
 
void Com(int idx, int cnt)
{
    if (cnt == m)
    {
        ans = min(ans, BFS());
        return;
    }
    for (int i = idx; i < p.size(); i++)
    {
        if (visited[i]) continue;
        visited[i] = 1;
        v.push_back(p[i]);
        Com(i, cnt + 1);
        v.pop_back();
        visited[i] = 0;
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> lab[i][j];
            if (lab[i][j] == 2)
                p.push_back({ i,j });//바이러스의 근원지 후보 좌표 저장
        }
    }
    Com(0, 0);
    ans = ans == MAX ? -1 : ans; //MAX면 -1대입
    cout << ans << '\n';
}