[백준 17142][C++] 연구소3 (Gold4)

[문제보기]

 17142. 연구소3

17142번: 연구소 3

 

[풀이과정]

이 문제를 풀기 위해 dfs와 bfs 알고리즘을 같이 사용을 했다.

활성 바이러스와 비활성 바이러스를 구별하기 위해 모든 바이러스를 vector virus에 저장하고

dfs 알고리즘을 이용하여 check[] 배열에 true값을 주어 활성 바이러스를 구별해준다. (조합사용)

 

그리고 active_virus() 함수를 사용하여 바이러스가 퍼지는 것을 구현하였다.

 

acvive_virus()

dfs()로 인해 check[]에 true값을 준 바이러스를 queue q에 넣고, bfs 알고리즘을 실행했다.

이 부분에서 temp[][] 배열을 새로 만들어 연산했는데, map[][] 배열에서 벽이 있는 위치를 살피면서

바이러스를 퍼뜨려준다.

그리고 비활성 바이러스에는 시간이 증가하지 않기때문에 if(map[nexty][nextx] == 0)을 사용하여 바이러스가

없는 부분에 대해서만 시간을 늘려주었다.

 

[소스코드]

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int n, m, emptyplace = 0;
vector<pair<int, int>> virus;
int map[50][50] = {0};
bool check[10];
pair<int, int> movdir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int ans = 987654321;
bool q_check[50][50];


void active_virus(){
    memset(q_check, false, sizeof(q_check));
    queue<pair<int, int>> q;
    int temp[50][50] = {0};
    int total = 0;
    int place = 0;

    for(int i=0; i<virus.size(); i++){
        if(check[i]){
            q.push({virus[i].first, virus[i].second});
            q_check[virus[i].first][virus[i].second] = true;
        }
    }

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nexty = y + movdir[i].first;
            int nextx = x + movdir[i].second;

            if(nexty < 0 || n <= nexty || nextx < 0 || n <= nextx)  continue;
            if(map[nexty][nextx] == 1) continue;
            if(q_check[nexty][nextx]) continue;


            temp[nexty][nextx] = temp[y][x] + 1;
            q_check[nexty][nextx] = true;
            if(map[nexty][nextx] == 0){
                place++;
                total = temp[nexty][nextx];
            }
            q.push({nexty, nextx});
        }        
    }

    if(emptyplace == place){
        ans = min(ans, total);
    }
}


void dfs(int idx, int cnt){
    if(cnt == m){
        active_virus();
        return;
    }

    for(int i=idx; i<virus.size(); i++){
        if(!check[i]){
            check[i] = true;
            dfs(i+1, cnt+1);
            check[i] = false;
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];

            if(map[i][j] == 0){
                emptyplace++;
            }
            else if(map[i][j] == 2){
                virus.push_back({i, j});
            }
        }
    }

    dfs(0, 0);

    if(ans == 987654321){
        cout << "-1";
    }
    else{
        cout << ans;
    }
}

 

[해결 과정 중 실수한 부분]

이 문제는 해결하는데 오래 걸린 문제이다. 구현은 처음부터 생각나서 했지만, 계속 틀리다고 나와서 코드를 다 지우고 

다시 짜봤는데도 계속 틀리다고 나왔다. 결국 블로그를 참고를 했는데, 문제 상에서 내가 잘못 이해를 하고 있었던 

것이였다. 

필자는 비활성바이러스도 벽으로 취급을 하여 연산을 진행했는데, 문제를 잘 읽어보니 비활성 바이러스에 대해서는 

인근 바이러스가 퍼지는 동시에 같이 변하는 뜻이였다.