[백준/구현/백트래킹/C++] 14502번 연구소 (삼성 코딩테스트 기출)

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

문제 해결 방법

문제는 크게 벽 세우기 -> 바이러스 퍼트리기 -> 안전영역 크기 구하기 이렇게 풀 수 있다.

처음에 입력을 받을 때 바이러스의 위치는 벡터 virus에, 빈칸 위치는 벡터 v_empty에 담았다.

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int x;
            cin >> x;
            MAP[i][j] = x;
            if(x == 2) virus.push_back({i,j});
            if(x == 0) v_empty.push_back({i,j});
        }
    }
}

 

벽은 3개만 세울 수 있는데 이걸 구하는 방법에 백트래킹을 사용했다.

벽은 빈곳에 세울 수 있기 때문에 v_empty를 사용했고 arr에는 v_empty의 인덱스를 담았다.

그리고 3개가 골라졌을 때 원본 MAP이 카피된 CMAP에 그 위치에 벽을 세웠다.

// 벽 세우기
void buildWall(int start, int cnt){
    if(cnt == 3){
        copyMap();
        for(int i=0; i<3; i++){
            CMAP[v_empty[arr[i]].first][v_empty[arr[i]].second] = 1;
        }
        spreadVirus();
        countSafe();
        return;
    }
    // 빈곳중에서 벽으로 만들 3개 선택
    for(int i=start; i<v_empty.size(); i++){
        if(!isVisited[i]){
            isVisited[i] = true;
            arr[cnt] = i;
            buildWall(i,cnt+1);
            isVisited[i] = false;
        }
    }
}

 

여기서 함수3개가 사용되는데 

우선 여러가지 방법으로 안전 영역을 구하게 되는데 입력받은  MAP에 바이러스를 표시하게 되면 다음 안전 영역을 구하는데 문제가 생기기 때문에 CMAP이라는 배열을 따로 만들어서 copyMap()을 사용하여 매번 MAP을 복사한다

마찬가지로  바이러스도 퍼져가면서 추가가 되는데 매번 추가되는 바이러스 위치가 다르기 때문에 cvirus벡터를 하나 더 만들어서 매번 리셋하여 사용한다

//지도 & 바이러스 원본 카피
void copyMap(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            CMAP[i][j] = MAP[i][j];
        }
    }
    cvirus.clear();
    for(int i=0; i<(int) virus.size(); i++){
        cvirus.push_back({virus[i].first, virus[i].second});
    }
}

 

바이러스가 퍼지는 함수 spreadVirus()는 cvirus에 들어있는 위치의 상하좌우를 탐색하면서 빈칸이면 바이러스를 퍼트리고 cvirus에 넣는다

함수에서 탈출하는 방법은 for문이 돌면서 바이러스가 새로 추가 될 때마다 count를 세고, 더 이상 늘지 않으면 탈출하게 만들었다

// 바이러스 퍼지기
void spreadVirus(){
    int size = cvirus.size();
    int count = 0;
    for(int i=0; i<size; i++){
        for(int j=0; j<4; j++){
            int x = cvirus[i].first + dx[j];
            int y = cvirus[i].second + dy[j];

            if(x<0 || y<0 || x>=n || y>=m || CMAP[x][y]!=0) continue;
            CMAP[x][y] = 2;
            cvirus.push_back({x,y});
            count++;
        }
    }
    if(count == 0) return;
    else spreadVirus();
}

 

그리고 결과인 안전영역을 구해주는데 0인 부분의 개수를 세고 최대값을 result에 넣어준다

// 안전 영역 구하기
void countSafe(){
    int count = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(CMAP[i][j] == 0) count++;
        }
    }
    result = max(result, count);
}

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
int MAP[9][9];
int CMAP[9][9];
int dx[] = {0, -1, 0, 1}; // 왼쪽, 위, 오른쪽, 아래
int dy[] = {-1, 0, 1, 0};
vector<pair<int, int>> virus;
vector<pair<int, int>> cvirus;
vector<pair<int, int>> v_empty;
int arr[4];
bool isVisited[100];
int result = 0;

//지도 & 바이러스 원본 카피
void copyMap(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            CMAP[i][j] = MAP[i][j];
        }
    }
    cvirus.clear();
    for(int i=0; i<(int) virus.size(); i++){
        cvirus.push_back({virus[i].first, virus[i].second});
    }
}

// 안전 영역 구하기
void countSafe(){
    int count = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(CMAP[i][j] == 0) count++;
        }
    }
    result = max(result, count);
}

// 바이러스 퍼지기
void spreadVirus(){
    int size = cvirus.size();
    int count = 0;
    for(int i=0; i<size; i++){
        for(int j=0; j<4; j++){
            int x = cvirus[i].first + dx[j];
            int y = cvirus[i].second + dy[j];

            if(x<0 || y<0 || x>=n || y>=m || CMAP[x][y]!=0) continue;
            CMAP[x][y] = 2;
            cvirus.push_back({x,y});
            count++;
        }
    }
    if(count == 0) return;
    else spreadVirus();
}

// 벽 세우기
void buildWall(int start, int cnt){
    if(cnt == 3){
        copyMap();
        for(int i=0; i<3; i++){
            CMAP[v_empty[arr[i]].first][v_empty[arr[i]].second] = 1;
        }
        spreadVirus();
        countSafe();
        return;
    }
    // 빈곳중에서 벽으로 만들 3개 선택
    for(int i=start; i<v_empty.size(); i++){
        if(!isVisited[i]){
            isVisited[i] = true;
            arr[cnt] = i;
            buildWall(i,cnt+1);
            isVisited[i] = false;
        }
    }
}

void input(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int x;
            cin >> x;
            MAP[i][j] = x;
            if(x == 2) virus.push_back({i,j});
            if(x == 0) v_empty.push_back({i,j});
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    buildWall(0, 0);
    cout << result;

    return 0;
}