[백준 14502] 연구소 (조합) (C/C++) (★★)

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
 
int map[10][10];
int mapCopy[10][10];
int N, M;
int Max;
 
pair<int, int> wall[100];
pair<int, int> virus[100];
int wallCnt, virusCnt;
 
queue<pair<int, int>> q;
int visited[10][10];
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
void copy()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            mapCopy[i][j] = map[i][j];
        }
    }    
}
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            visited[i][j] = 0;
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int zeroCount()
{
    int cnt = 0;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == 0)
            {
                cnt++;
            }        
        }
    }
    
    return cnt;
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
// BFS
void spread_virus(int x, int y)
{
    visited[x][y] = 1;
    q.push({x, y});
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(map[xpos][ypos] != 1 && safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                map[xpos][ypos] = 2;
            }
        }    
    }
}
 
// DFS + 조합 
void make_wall(int idx, int cnt)
{
    if(cnt == 3)
    {
        copy();
        
        for(int i = 0; i < virusCnt; i++)
        {
            spread_virus(virus[i].first, virus[i].second);
        }
        
        int val = zeroCount();
        
        if(val > Max)
        {
            Max = val;
        }
        
        init();
        
        return;
    }    
    
    for(int i = idx; i < wallCnt; i++)
    {
        map[wall[i].first][wall[i].second] = 1;
        make_wall(i+1, cnt+1);
        map[wall[i].first][wall[i].second] = 0;
    }
}
 
void simulation()
{
    make_wall(0, 0);
}
 
int main(void)
{
//    freopen("B14502_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
            mapCopy[i][j] = map[i][j];
            
            if(map[i][j] == 0)
            {
                wall[wallCnt].first = i;
                wall[wallCnt++].second = j;
            }
            else if(map[i][j] == 2)
            {
                virus[virusCnt].first = i;
                virus[virusCnt++].second = j;
            }
        }
    }
    
    simulation();
    
    cout << Max;
    
    return 0;
}