[삼성SW역량테스트/DFS] 14502 연구소

DFS를 활용하는 약간은 응용된 문제

그냥 단순히 바이러스인 2를 퍼트리는것 자체는 별로 어렵지 않다. 그냥 DFS혹은 BFS를 사용하면 된다.

하지만 기둥인 1을 3개 세워야 하기 때문에 좀 생각을 해야 한다.

기둥을 3곳에 세워야 하는데 이거는 그냥 모든 경우의수를 다 해 보는 수 밖에 없다.

따라서 처음에 입력을 받을때 0인곳의 위치를 벡터에 넣어 놓고 나중에 그 벡터에 있는 값중 3개를 차례차례 중복되지 않게 꺼낸 다음

그 세곳에 기둥을 세워 놓고 나서 DFS를 돌린다. DFS를 돌리면 바이러스가 퍼질것이고(2) 그리고 나서 안전 영역의 수를 카운트 하며, 안전 영역 크기의 최대값을 갱신한다.

위의 과정을 벡터에 있는 모든 0의 3개 조합에 대해서 전부 수행했을때의 안전영역의 최대값이 정답이 된다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int plusX[4] = {-1,0,1,0};
int plusY[4] = {0,1,0,-1};
int n,m;
int map[8][8];
int copymap[8][8];
vector<pair<int,int>> v;
 
void DFS(int x,int y){ //바이러스를 퍼트리기 위한 DFS
    for(int i=0; i<4; i++){
        int newX = plusX[i] + x;
        int newY = plusY[i] + y;
        if(newX>=0 && newX<n && newY>=0 && newY<m){
            if(copymap[newX][newY]==0){
                copymap[newX][newY] = 2;
                DFS(newX,newY);
            }
        }
    }
}
 
 
int main(){
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>map[i][j];
            copymap[i][j] = map[i][j];
            if(!map[i][j]) v.push_back(make_pair(i,j)); //0인 안전 영역의 위치만 벡터에 넣기. 그래야 0인곳의 위치 3개를 뽑아서 기둥 3개를 설치할수 있음.
        }
    }
    int MAX = 0;
    for(int i=0; i<v.size()-2; i++){
        for(int j=i+1; j<v.size()-1; j++){
            for(int k=j+1; k<v.size(); k++){
                pair<int,int> one = v[i];
                pair<int,int> two = v[j];
                pair<int,int> three = v[k]; //3개의 좌표 선택
                
                for(int i=0; i<n; i++){
                    for(int j=0; j<m; j++){
                        copymap[i][j] = map[i][j];
                    }
                }
                
                //3개의 기둥 세우기
                copymap[one.first][one.second] = 1;
                copymap[two.first][two.second] = 1;
                copymap[three.first][three.second] = 1;
                
                for(int i=0; i<n; i++){
                    for(int j=0; j<m; j++){
                        if(copymap[i][j] == 2)
                            DFS(i,j);
                    }
                } //기둥세우고 나서 DFS돌려서 바이러스 전파 시키기
                
//                cout<<endl;
//                for(int i=0; i<n; i++){
//                    for(int j=0; j<m; j++){
//                        cout<<copymap[i][j]<<" ";
//                    }cout<<endl;} //바이러스 잘 전파됬는지 확인하기
                
                int cnt = 0; //안전 영역 크기 확인
                for(int i=0; i<n; i++){
                    for(int j=0; j<m; j++){
                        if(copymap[i][j] == 0)
                            cnt ++;
                    }
                }
                MAX = max(MAX,cnt);
            }
        }
    }
    cout<<MAX<<endl;
    
    
    
    return 0;
}