[Baekjoon,14502]연구소

해결

이 문제는 크게 두 부분으로 나눌 수 있다. 하나는 “주어진 맵에서 벽을 어떻게 세우는가?” 이고, 다른 하나는 “바이러스를 어떻게 퍼뜨릴까?” 이다.

무식하게 벽을 세우자

가장 먼저 떠오르는 방법은 모든 벽이 세워질 수 있는 경우의 수를 전부 이용해 보며 바이러스를 퍼뜨리는 것이다.

현재 위치 (x,y)에 대하여 아직 벽이 3개가 세워지지 않았을 때

1. 벽을 세운다.
2. 벽을 세우지 않는다.

위와 같은 과정을 재귀적으로 구현하면 된다. 이때 map을 전역 변수로 사용하기 때문에 벽을 세우고 다음 탐색을 위해 다시 벽을 허물어야 한다.

int H,W;
vector<vector<int> > map;
int maxSize;
// 벽이 하나씩 세우며 벽이 3개가 세워진 경우 countSafety()를 호출하여 
// maxSize보다 큰 경우 maxSize를 갱신한다.
void calcMaxSize(int n, int y, int x)
{
    if(n==3)
    {
        maxSize=max(maxSize,countSafety());
        return;
    }
    if(!inRange(y,x))
        return;
    
    // 다음 칸 위치
    int ny=y, nx=x+1;
    if(nx>=W)
    {
        ++ny;
        nx=0;
    }
    
    // 현재 위치에 벽을 세움
    if(map[y][x]==EMPTY)
    {
        map[y][x]=WALL;
        calcMaxSize(n+1,ny,nx);
        map[y][x]=EMPTY;
    }
    // 현재 위치에 벽을 안 세움
    calcMaxSize(n,ny,nx);
}

BFS를 이용해 바이러스를 퍼뜨리자

벽을 세웠으면 바이러스를 퍼뜨리면 된다. 바이러스는 BFS를 통해 퍼뜨리면 된다. 이때 발원지가 여러군데 있을 수 있으므로 이를 전부 queue에 추가하고 dicovered를 true로 해주여야 한다. 다음 칸이 범위를 벗어났거나 빈 칸이 아닌 경우 탐색하지 않는다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX_N=8;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};

enum{ EMPTY, WALL, VIRUS };

int H,W;
vector<vector<int> > map;
bool discovered[MAX_N][MAX_N];
int maxSize;

inline bool inRange(int y, int x)
{
    return 0<=y && y<H && 0<=x && x<W;
}

// BFS를 통해 iMap에 바이러스를 퍼뜨린다.
void infect(vector<vector<int> >& iMap, queue<pair<int,int> >& q)
{
    while(!q.empty())
    {
        pair<int,int> here=q.front();
        q.pop();
        for(int dir=0;dir<4;++dir)
        {
            int ny=here.first+dy[dir], nx=here.second+dx[dir];
            // 범위를 벗어나거나 빈 칸이 아닌 경우
            if(!inRange(ny,nx) || iMap[ny][nx]!=EMPTY)
                continue;
            discovered[ny][nx]=true;
            q.push(make_pair(ny,nx));
            // 바이러스 확산
            iMap[ny][nx]=VIRUS;
        }
    }
}

// 현재 map에서 바이러스가 퍼졌을 때 안전 구역의 크기를 구한다. 
int countSafety()
{
    vector<vector<int> > infectedMap=map;
    queue<pair<int,int> > q;
    memset(discovered,false,sizeof(discovered));
    // 바이러스 시작 부분 초기화
    for(int i=0;i<H;++i)
        for(int j=0;j<W;++j)
            if(map[i][j]==VIRUS)
            {
                q.push(make_pair(i,j));
                discovered[i][j]=true;
            }
    
    // 바이러스가 퍼진다
    infect(infectedMap,q);
    
    int ret=0;
    for(int i=0;i<H;++i)
        for(int j=0;j<W;++j)
            if(infectedMap[i][j]==EMPTY)
                ++ret;
    return ret;
}

// 벽이 하나씩 세우며 벽이 3개가 세워진 경우 countSafety()를 호출하여 
// maxSize보다 큰 경우 maxSize를 갱신한다.
void calcMaxSize(int n, int y, int x)
{
    if(n==3)
    {
        maxSize=max(maxSize,countSafety());
        return;
    }
    if(!inRange(y,x))
        return;
    
    // 다음 칸 위치
    int ny=y, nx=x+1;
    if(nx>=W)
    {
        ++ny;
        nx=0;
    }
    
    // 현재 위치에 벽을 세움
    if(map[y][x]==EMPTY)
    {
        map[y][x]=WALL;
        calcMaxSize(n+1,ny,nx);
        map[y][x]=EMPTY;
    }
    // 현재 위치에 벽을 안 세움
    calcMaxSize(n,ny,nx);
}

int main()
{
    cin>>H>>W;
    map=vector<vector<int> >(H,vector<int>(W));
    for(int i=0;i<H;++i)
        for(int j=0;j<W;++j)
            cin>>map[i][j];
    
    maxSize=0;
    calcMaxSize(0, 0, 0);
    cout<<maxSize<<endl;
    return 0;
}