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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
//벽은 3개 세울 수 있음
//벽을 모든 빈칸에 3개 세워보고 안전영역 최대 크기 출력
 
int lab[9][9];
int cop[9][9]; //연구소의 카피
int ck[9][9];
bool visited[8 * 8];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
vector<pair<int, int>>p, v;
int n, m, ans;
 
int BFS()
{
    int cnt = 0;
    memset(ck, 0, sizeof(ck));
    queue <pair<int, int>> q;
    for (int i = 1; i <= n; i++) //BFS함수 한번 호출시 연구소 맵을 copy해줌
    {
        for (int j = 1; j <= m; j++)
        {
            cop[i][j] = lab[i][j];
        }
    }
    for (int i = 0; i < v.size(); i++) {
        cop[v[i].first][v[i].second] = 1;
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (cop[i][j] == 2)
            {
                q.push({ i,j });
                ck[i][j] = 1;
            }
        }
    }
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
            for (int j = 0; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (1 <= nx && nx <= n && 1 <= ny && ny <= m)//map안에 있으면
                {
                    if (ck[nx][ny] == 0 && cop[nx][ny]!=1) //연구소가 벽이 아니면
                    {
                        cop[nx][ny] = 2; //그 방 오염시킨다
                        ck[nx][ny] = 1; //체크해주고
                        q.push({ nx,ny }); //방을 큐에 넣어준다
                    }
                }
            }
    }
 
    for (int i = 1; i <= n; i++)//오염된 후 연구소의 방이 0인 것만 count
    {
        for (int j = 1; j <= m; j++)
        {
            if (cop[i][j] == 0)
                cnt++;
        }
    }
    return cnt;
}
 
void Com(int idx,int cnt) { //모든 조합에 따라 bfs를 돌려본다.
 
    if (cnt == 3)
    {
        ans = max(ans, BFS());
        return;
    }
    for (int i = idx; i <p.size(); i++)
    {
        if (visited[i])continue;
        visited[i] = true;
        v.push_back(p[i]);
        Com(i, cnt + 1);
        v.pop_back();
        visited[i] = false;
    }
}
 
int main() {
    cin >> n >> m; // n*m행렬
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
        {
            cin >> lab[i][j];
            if (!lab[i][j])p.push_back({ i,j });
        }
    }
    Com(0,0);
    cout << ans << '\n';
}