삼성 SW 역량테스트 기출 :: 연구소

문제링크 : https://www.acmicpc.net/problem/14502

난이도 : 중

 

/*
 * 연구소 : https://www.acmicpc.net/problem/14502
 */

#include <stdio.h>
#include <iostream>
#include <vector>

#define FOR(i, n) for(int i = 0 ; i < n; i ++)
using namespace std;

int n, m, mmin, wall, total;
vector<pair<int, int>> empty;
vector<pair<int, int>> virus;
vector<vector<int>> map;

void init(){
    cin >> n >> m;
    map.resize(n);
    FOR(i, n) {
        map[i].resize(m);
        FOR(j, m) {
            cin >> map[i][j];
            if (map[i][j] == 0) empty.push_back(make_pair(i, j));
            if (map[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
    mmin = INT32_MAX;
    wall = n*m-empty.size()-virus.size();
}
// 해당 인덱스가 보드 안의 범위인지 확인
bool inBoard(int first, int second){
    if(first < 0 || second < 0 || first >= n || second >= m) return false;
    return true;
}
// 해당 인덱스가 보드 안에 있고 빈칸일경우에 그 칸으로 바이러스를 퍼트림
// cmap에 바이러스가 퍼졌음을 표시하고 전체 바이러스 갯수에도 더 함
void pushVirus(vector<vector<int>> &cmap, vector<pair<int, int>> &spread, int i, int j){
    if(inBoard(i, j)&&cmap[i][j]==0){
        spread.push_back(make_pair(i,j));
        cmap[i][j]=2;
        total++;
    }
}
// cmap 상태에서 바이러스가 퍼질 수 있는 총 칸의 수를 반환
int countSafe(vector<vector<int>> cmap, vector<pair<int, int>> spread) { // ******** 벡터 parameter넘길 때 & 없으면 값복사 있으면 참조
    total = virus.size();
    while (spread.size() > 0) {
        int first = spread.front().first;
        int second = spread.front().second;
        spread.erase(spread.begin());
        pushVirus(cmap, spread, first+1, second);
        pushVirus(cmap, spread, first-1, second);
        pushVirus(cmap, spread, first, second+1);
        pushVirus(cmap, spread, first, second-1);
    }
    return total;
}
void solve(){
    //이 세 위치에 벽을 놓고
    for(int i = 0 ; i < empty.size()-2; i++){
        map[empty[i].first][empty[i].second] = 1;
        for(int j = i+1; j<empty.size()-1; j++){
            map[empty[j].first][empty[j].second] = 1;
            for(int k = j+1; k<empty.size(); k++){
                map[empty[k].first][empty[k].second] = 1;
                mmin = min(countSafe(map, virus), mmin);
                map[empty[k].first][empty[k].second] = 0;
            }
            map[empty[j].first][empty[j].second] = 0;
        }
        map[empty[i].first][empty[i].second] = 0;
    }
}
int main(){
    init();
    solve();
    cout << n*m-mmin-wall-3 << endl;
}