[백준] 14502 연구소

문제를 해결하는 아이디어는 가장 넓은 안전 영역을 구하는 것이므로 벽을 설치한 후 바이러스를 퍼트려보고 완료된 그래프를 탐색하여 안전영역의 개수를 출력하면 되는 문제이다.

바이러스를 퍼트리고 안전영역을 찾는건 정말 쉬운 문제인데.. 이놈의 벽..!

 

해당 문제를 처음 딱 읽고 이해는 갔지만 이 벽이 문제였다.

벽 3개를 어떻게 배치를 할 것인가..

 

처음에 반복문을 이용하여 배치를 해보았지만 내 구현 능력이 부족한지 계속해서 실패하였다. ㅜㅜ

 

결국.. 인터넷의 힘을 빌릴 수 밖에..ㅠ

 

재귀를 이용하여 벽을 세우는데 약간 신기했다. (새로운 패턴 익히는 중)

 

□ 소스코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> inputOrginal14502(9,vector<int>(9,0));
vector<vector<int>> input14502(9,vector<int>(9,0));
vector<pair<int, int>> virus14502;
int maxCount14502 = 0;

void copy14502(int N, int M){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            input14502[i][j] = inputOrginal14502[i][j];
}

void bfs14502(int N, int M){
    copy14502(N, M);
    queue<pair<int, int>> q;
    
    for(int i=0;i<virus14502.size();i++)
        q.push({virus14502[i].first,virus14502[i].second});
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        
        for(int i=0;i<4;i++){
            int mx = dx[i] + x;
            int my = dy[i] + y;
            
            if(mx <1 || my <1 || mx > N || my > M)
                continue;
            
            if(input14502[mx][my] == 0 ){
                q.push({mx,my});
                input14502[mx][my] = 2;
            }
        }
    }
    
    int maxArange = 0;
    for(int i=1;i<=N;i++)
        for(int j=1; j<=M; j++)
            if(input14502[i][j] == 0)
                maxArange++;
    
    maxCount14502 = max(maxArange,maxCount14502);
}

void buildWall(int count,int N,int M){
    if(count == 0){
        bfs14502(N, M);
        return;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(inputOrginal14502[i][j] == 0 ){
                inputOrginal14502[i][j] = 1;
                count--;
                buildWall(count, N, M);
                count++;
                inputOrginal14502[i][j] = 0;
                
            }
        }
    }
    
}

void lab14502(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,M; cin>>N>>M;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            int a; cin>>a;
            inputOrginal14502[i][j] = a;
            input14502[i][j] = a;
            if(a==2)
                virus14502.push_back({i,j});
        }
    }
    
    buildWall(3,N,M);
    bfs14502(N, M);
    
    cout<<maxCount14502<<endl;
}