백준 14502문제

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

int N,M;

int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};


int dfs(int x, int y,int arr[][11]){
    int ret = 1;
    for(int i = 0; i < 4 ; i++){
        int nextX = x+X[i] , nextY = y+Y[i];
        if((nextX >= 1 && nextX <= N) && ( nextY > 0 && nextY <=M)){
            if(!arr[nextX][nextY]){
                arr[nextX][nextY] = 2;
                ret += dfs(nextX,nextY, arr);
            }
        }
    }
    return ret;
}


int main(){ 
    ios_base::sync_with_stdio(false);


    int arr[11][11];
    int visit[11][11] = {0,};
    int ans = 0;
    int ones = 0;
    vector<pair<int,int>> posV, posZ;

    cin >>  N >> M;

    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j <= M ; j++){
            cin >> arr[i][j];
            if( arr[i][j] == 2)
                posV.pb(make_pair(i,j));
            else if(arr[i][j] == 0)
                posZ.pb(make_pair(i,j));
            else
                ones += 1;
        }

    int arrr[11][11] = {0,};
    int zeros = posZ.size();
    for(int i = 0 ; i< zeros ; i++){
        if(arr[posZ[i].first][posZ[i].second]) continue;
        for(int j = i + 1 ; j<zeros ; j++){
            if(arr[posZ[j].first][posZ[j].second]) continue;
            for(int k = j + 1 ; k<zeros ; k++){
                if(arr[posZ[k].first][posZ[k].second]) continue;
                arr[posZ[i].first][posZ[i].second] = 1;
                arr[posZ[j].first][posZ[j].second] = 1;
                arr[posZ[k].first][posZ[k].second] = 1;
                int copy_arr[11][11]={0,};
                memcpy(copy_arr, arr, sizeof(arr));
                int twos = 0;
                for(auto a : posV)
                    twos += dfs(a.first, a.second,copy_arr);
                
                ans = max(ans, N*M - twos - ones - 3);
                arr[posZ[i].first][posZ[i].second] = 0;
                arr[posZ[j].first][posZ[j].second] = 0;
                arr[posZ[k].first][posZ[k].second] = 0;

            }
        }
    }
    cout << ans << endl;

    return 0;
}

DFS를 이용한 문제풀이입니다.