연구소

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int a[9][9];
vector<pair<int, int>> v1;
vector<pair<int, int>> v2;
vector<pair<int, int>> v3;
int d[9][9];
bool f[9][9];
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};

void re(){
    for(int i = 0; i < v1.size(); i++){
        int x = v1[i].first;
        int y = v1[i].second;
        d[x][y] = 0;
    }
    for(int i = 0; i < v2.size(); i++){
        int x = v2[i].first;
        int y = v2[i].second;
        d[x][y] = 2;
    }
    for(int i = 0; i < v3.size(); i++){
        int x = v3[i].first;
        int y = v3[i].second;
        d[x][y] = 1;
    }
    for(int i = 0; i < 9; i ++){
        for(int j =0; j < 9; j++)
            f[i][j] = false;
    }
}

void bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    d[x][y] = 2;
    f[x][y] = true;
    while(!q.empty()){
        x = q.front().first; y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+ dx[i]; int ny = y+dy[i];
            if(nx>= 0 &&nx <n &&ny>=0 &&ny < m) {
                if (f[nx][ny] == false) {
                    if (d[nx][ny] == 0) {
                        f[nx][ny] = true;
                        d[nx][ny] = 2;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m;j++){
            scanf("%d", &a[i][j]);
            if(a[i][j] == 0) v1.push_back(make_pair(i,j));
            if(a[i][j] == 2) v2.push_back(make_pair(i,j));
            if(a[i][j] == 1) v3.push_back(make_pair(i,j));
        }
    }
    re();
    vector<int> s;
    for(int i = 0; i< v1.size() - 3; i++){
        s.push_back(0);
    }
    s.push_back(1);
    s.push_back(1);
    s.push_back(1);
    int result = 0;
    vector<int> qq;
    do{
        int zero = 0;
        vector<pair<int, int>> il;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 1){
                int x = v1[i].first;
                int y = v1[i].second;
                il.push_back(make_pair(x,y));
            }
        }

        for(int i = 0; i < il.size(); i++){
            d[il[i].first][il[i].second] = 1;
        }

        for(int i = 0; i < v2.size(); i++){
            bfs(v2[i].first, v2[i].second);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(d[i][j] == 0)
                    zero +=1;
            }
        }
        if(zero > result)
            result = zero;
        qq.push_back(zero);
        re();
    }while(next_permutation(s.begin(), s.end()));
    //for(int i = 0; i < qq.size(); i++)
      //  printf("%d", qq[i]);
    //printf("\n");

    printf("%d\n", result);
    return 0;


}

BFS로만 하다가, 배열크기가 최대 8,8이길래 브루트포스 곁들여서 진행함

permutation 돌려서, 0의 위치 를 세개 계속 1로바꿔주고 진행해봄