[백준] 14502 문제: 연구소

https://www.acmicpc.net/problem/14502

벽(1)을 3개를 설치했을 때 바이러스(2)가 퍼졌을 때 안전구역(0)이 최대로 많이 남았을 때의 수를 구하는 문제이다. 이 문제는 BFS(DFS)와 조합(Combination) 문제이다.
BFS는 간단하다. 상하좌우로 움직이되 안전구역(0) 일 때만 바이러스(2)가 퍼진다.

문제는 벽 3개를 어떻게 설치를 하는 것인가이다. 나는 이를 조합으로 문제를 풀었는데, 우선 빈 공간의 최대갯수는 8 X 8 - 1(바이러스) = 63개이다. 이 중에서 벽을 3개를 치게되는데 이는 63C3 = 39711개이다. 만약 바이러스 하나가 각 공간 하나를 방문한다고 생각하면 최대 계산량은 63 X 39711 = 2501793개로 계산량이 그렇게 많지 않다.

조합으로 어떻게 푸느냐가 문제인데, 난 next_permutation함수를 이용해 문제를 풀었다. next_permutation은 순열을 구하는 함수이다. 나는 vector v에 1이 3개, 0은 (arr의 0의 갯수 - 3)인 순열을 만들었다. 그러면 next_permutation은 v의 다음 순열을 구하게 될 것인데 v 값들 중에 1이 될 때의 index와 0의 좌표를 넣어둔 vector의 index를 매칭을 하게되면 조합처럼 된다. 이 떄 0의 좌표를 1로 바꾸어 BFS 함수를 사용해 0의 수를 비교해 가장 큰 값이 나올때까지 이러한 일을 반복하는 것이다.
BFS가 종료가 되었을 때에는 1로 바꾸었던 좌표들을 다시 0으로 바꿔줘야한다.

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

using namespace std;

int arr[8][8] = {0, };
int N, M, zeronum, onenum;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int BFS(queue<pair<int, int> > q){
    int x, y, nx, ny, ret;
    ret = 0;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        ret++;
        for(int i = 0; i<4; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(arr[nx][ny] == 0 && nx >= 0 && ny >= 0 && nx<N && ny < M){
                q.push(make_pair(nx, ny));
                arr[nx][ny] = 2;
            }
        }
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    zeronum = 0;
    onenum = 0;
    queue<pair<int, int> > q, q1;
    vector<pair<int, int> > v;
    vector<int> v1;
    int minum = -1;
    scanf("%d %d", &N, &M);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            scanf("%1d", &arr[i][j]);
            if(arr[i][j] == 0){
                v.push_back(make_pair(i, j));
                zeronum++;
            }
            else if(arr[i][j] == 2){
                q.push(make_pair(i, j));
            }
            else{
                onenum++;
            }
        }
    }
    
    for(int i = 0; i<3 ;i++)
        v1.push_back(1);
    for(int i = 0; i< zeronum-3 ; i++)
        v1.push_back(0);
    
    sort(v1.begin(), v1.end());
    
    do{
        for(int i = 0; i< v1.size(); i++){
            if(v1[i] == 1)
                arr[v[i].first][v[i].second] = 1;
            q1.push(v[i]);
        }
        
        minum = max(minum, (N * M) - (BFS(q) + onenum + 3));
        
        while(!q1.empty()){
            arr[q1.front().first][q1.front().second] = 0;
            q1.pop();
        }

    }while (next_permutation(v1.begin(), v1.end()));

    printf("%d\n", minum);
}