[백준] 연구소

삼성 기출 문제중 하나이다. 3개의 벽을 꼭 설치해야 하고 모든 바이러스가 상하좌우로 퍼진다는 가정하에 가장 많은 안전지대를 만들면 된다. 결국 이 문제의 핵심은 어느 위치에 벽을 두냐에 로직이였고 아이디어만 떠올리면은 쉽게 풀 수 있는 문제다.

솔직히 이 문제를 30분정도 고민했는데 좋은 방법으로 최적의 위치를 한번에 생각하는게 아무리 생각해도 불가능 했다.

1. 바이러스 기준 벽 찾기
2. 벽 기준 벽 찾기
3. 공기 기준 벽 찾기

세가지의 선택권을 가지고 최적의 위치를 찾으려고 했지만 1번과 2번은 도저히 불가능했다. 그리고 이 문제가 완전탐색 이라는 특징을 가진걸 사실 처음부터 알아야 했는데 이것때매 너무 헤맸다. 완전탐색 문제의 특징은 정말 모든 가능성을 눈에 두고 생각해야한다. 애초에 특정 알고리즘으로 최적의 벽 위치를 찾는거는 1번과 2번을 시도해본 결과 불가능했다. 결국 남은건 모든 경우의 수를 다 탐색해보는것.

결국 시도한건 공기를 기준으로 dfs를 진행했고 벽이 3개가 됐을때 바이러스의 위치에서 bfs 시뮬레이션을 해서 확보 가능한 안전지역을 구한다음에 최대 값으로 기록해주었다. 이 문제의 솔루션은 모든 공기에서 조합으로 벽을 모두 설치하고 계산해야 했던거라 내가 좀 헤맸던거같다, 앞으로 조심해야겠다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N,M; 
int answer = -1; 
int matrix[9][9];
bool visited[9][9]; 
vector<pair<int,int>> airVec; 
queue<pair<int,int>> q_global; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 


void Input(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
            if(matrix[i][j] == 0){
                airVec.push_back({i,j}); 
            }
            if(matrix[i][j] == 2){
                q_global.push({i,j}); 
            }
        }
    }
}

void bfs(queue<pair<int,int>>& q, int& safeZone){

    while(!q.empty()){
        int size = q.size(); 
        for(int i = 0; i < size; i++){
            pair<int,int> first = q.front(); 
            q.pop(); 

            int x = first.first, y = first.second; 
            visited[x][y] = true; 

            for(pair<int,int>& p : dir){
                int nX = x + p.first;
                int nY = y + p.second; 

                if(nX < 0 || nX >= N || nY < 0 || nY >= M || visited[nX][nY] || matrix[nX][nY] != 0) continue; 

                visited[nX][nY] = true; 
                q.push({nX,nY}); 
                safeZone--; 
            }
        }
    }
}

void dfs(int index,int& cnt){
    if(cnt == 3){
        queue<pair<int,int>> copyQ = q_global; 
        int safeZone = airVec.size() - 3; 
        memset(visited,false,sizeof(visited)); 
        bfs(copyQ,safeZone); 
        answer = max(answer,safeZone); 
        return; 
    }
    for(int i = index; i < airVec.size(); i++){
        int x = airVec[i].first, y = airVec[i].second; 
        matrix[x][y] = 1; 
        dfs(i+1,cnt+=1); 
        cnt -= 1; 
        matrix[x][y] = 0; 
    }
}

void Solution(){
    int cnt = 0; 
    dfs(0,cnt); 
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}