[백준-삼성SW역량테스트 기출] 14502번. 연구소 C++

www.acmicpc.net/problem/14502

14502번: 연구소

>문제 설명

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

풀이

 완전탐색 문제이다. 우선 빈칸 중에 3개를 선택해 벽으로 만들어 주고, 바이러스 위치를 기준으로 DFS를 돌리며 갈 수 있는 칸의 개수를 구한다. 가능한 조합의 경우에 대해 DFS를 수행해줄 때마다, visited배열 초기화와, 선택된 3칸에 대해 벽으로 만들기(값 1로 변경)을 해주고, DFS를 수행한 후 다시 빈칸(값 0)으로 만들어주었다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;

int n, m;
vector<pair<int,int>> blank, virus, wall;
int map[9][9] = {0, };
bool visited[9][9];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int sum = 0;

bool checkbound(int x, int y){
    return x>=0 && x<n && y>=0 && y<m && visited[x][y] == false && map[x][y] == 0;
}


int dfs(){
    
    stack<pair<int,int>> s;
    int counting = 0;
    
    for(int i=0; i<virus.size(); i++){
        s.push({virus[i].first, virus[i].second});
    }
    
    while(!s.empty()){
        
        int cx = s.top().first;
        int cy = s.top().second;
        s.pop();
        
        for(int i=0; i<4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            if(checkbound(nx, ny)){
                visited[nx][ny] = true;
                s.push({nx, ny});
                counting++;
            }
        }
        
    }
    
    return counting;
}

int solve(){
    
    int result = -1;
    
    for(int i=0; i<blank.size()-2; i++){
        for(int j=i+1; j<blank.size()-1; j++){
            for(int k=j+1; k<blank.size(); k++){
                
                //배열 초기화
                memset(visited, false, sizeof(visited));
                
                //map정보 변경
                map[blank[i].first][blank[i].second] = 1;
                map[blank[j].first][blank[j].second] = 1;
                map[blank[k].first][blank[k].second] = 1;
                
                //2 퍼질 수 있는 개수 카운팅
                int count = dfs();
                //cout<<count<<"\n";
                result = max(result, (int)blank.size() - count - 3);
                //cout<<"result: "<<result<<"\n";
                
                //map 돌리기
                map[blank[i].first][blank[i].second] = 0;
                map[blank[j].first][blank[j].second] = 0;
                map[blank[k].first][blank[k].second] = 0;
            }
        }
    }
    
    return result;
}

int main()
{
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>map[i][j];
            if(map[i][j] == 0){
                blank.push_back({i, j});
            }
            else if(map[i][j] == 1){
                wall.push_back({i, j});
            }
            else{
                virus.push_back({i, j});
            }
        }
    }
    
    //cout<<"blank counting: "<<blank.size()<<"\n";
    
    cout<<solve()<<"\n";
    
    return 0;
}

 ** 맨 처음 입력받을 때, wall(벽) 정보 vector도 만들어줬는데 쓸데 없음!! 삭제해도됨!!