[14502] 연구소

이 문제도 N이 작기 때문에 3개의 기둥을 한번씩 다 세워보고 최대값을 찾는 완전탐색 문제입니다.

dfs는 기둥을 세우는 함수이며, 깊이가 3이 되었을 때(기둥을 세개 세웠을 때) bfs함수를 호출합니다.

bfs는 바이러스가 퍼지는 함수 입니다. bfs가 끝나면 recovery함수를 호출해서 바이러스가 퍼지기 전의 맵 상태로 돌리며,

돌릴 때 0의 개수도 같이 세서 리턴하는 함수입니다.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 8
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
 
vector<pair<int, int> > virus;
 
void input()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
 
            if(map[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
}
 
void copy_map(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
 
int recovery(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    int ret = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(a[i][j] == 0) ret++;
            a[i][j] = b[i][j];
        }
    }
    return ret;
}
 
void bfs()
{
    queue<pair<int, int> > q;
    for(int i = 0; i < virus.size(); i++) q.push(virus[i]);
 
    while(!q.empty())
    {
        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(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
            map[nx][ny] = 2;
            q.push(make_pair(nx, ny));
        }
    }
}
 
void dfs(int x, int y, int d)
{
    map[x][y] = 1;
    visit[x][y] = 1;
 
    if(d == 3)
    {
        //bfs
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
 
        bfs();
        max_value = max(max_value, recovery(map, tmp));
 
        visit[x][y] = 0;
        map[x][y] = 0;
        return;
    }
 
    for(int i = x; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(visit[i][j] || map[i][j] != 0) continue;
            dfs(i, j, d + 1);
        }
    }
 
    map[x][y] = 0;
    visit[x][y] = 0;
}
 
void process()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] != 0) continue;
            dfs(i, j, 1);
        }
    }
 
    printf("%d\n", max_value);
}
 
int main()
{
    input();
    process();
 
    return 0;
}