17142번-연구소3

문제

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

17142번: 연구소 3

---

접근방법

1) 접근 사고

바이러스의 경우를 조합으로 구현하여 바이러스가 퍼질 수 있는 모든 경우의 수를 BFS를 사용하여 탐색하였습니다. 주의해야 할 점은 BFS를 사용하여 시간을 측정할 때 0의 갯수를 cnt해서 바이러스가 모두 퍼져있는지의 유무의 형태로 작성하신다면 중간에 탐색을 통한 cnt 갯수가 0의 모든 갯수와 일치한 경우 탐색을 종료하는 조건절을 추가하셔야 합니다. 그렇지 않으면 모두 탐색해도 q안에는 중복 방문값이 남아있기 때문에 정확한 시간을 측정하기 어려울 것입니다.

 

2) 시간 복잡도

O(V + E)

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 
const int MAX = 51;
int board[MAX][MAX];
bool visited[MAX][MAX];
int n, m;
int ret = INT_MAX;
int vNum, zeroCnt;
vector<pair<int, int>> virus;
int my[] = {-1,1,0,0};
int mx[] = {0,0,-1,1};
int main() {
    fastio;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] == 2) {
                //조합의 경웅의 수를 만들 때 사용할 바이러스들을 저장합니다.
                virus.push_back({i, j});
                //조합을 구할 때 사용하기 위한 바이러스 갯수
                vNum++;
            }
            //모든 바이러스가 퍼졌는지 확인할 때 사용하기 위한 0의 갯수를 측정한 변수
            if(board[i][j] == 0){
                zeroCnt++;
            }
        }
    }
    
    //바이러스의 조합을 만드는과저 예제1 기준 00111 ~ 11100 까지의 모든 경우를 탐색
    vector<int> vArr;
    for (int i = 0; i < m; i++) {
        vArr.push_back(1);
    }
    for (int j = 0; j < vNum - m; j++) {
        vArr.push_back(0);
    }
    sort(vArr.begin(), vArr.end());
 
    int a = 0;
    do {
        memset(visited, false, sizeof visited);
        queue<pair<int, int>> q;
        for (int i = 0; i < vArr.size(); i++) {
            if (vArr[i] == 1) {
                q.push({virus[i].first, virus[i].second});
                visited[virus[i].first][virus[i].second] = true;
            }
        }
 
        int cnt = 0;
        int checkZc =0;
        while (!q.empty()) {
 
            //0을 확인한 갯수가 0의 총 갯수와 같다면 탐색 종료
            if(checkZc == zeroCnt){
                break;
            }
            int qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                auto[y, x] = q.front();
                q.pop();
 
                for (int d = 0; d < 4; d++) {
                    int ny = y + my[d];
                    int nx = x + mx[d];
                    if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
                        if (!visited[ny][nx]){
                            //0이라면 0탐색 갯수를 올려주고 다음 탐색을 위한 q.push
                            if(board[ny][nx] == 0){
                                q.push({ny, nx});
                                visited[ny][nx] = true;
                                checkZc++;
                            }
                            //탐색 경우가 비활성화 바이러스라면 다음 탐색 때 활성화 시켜주기 위한 q.push
                            if(board[ny][nx] == 2){
                                visited[ny][nx] = true;
                                q.push({ny, nx});
                            }
                        }
                    }
                }
            }
            cnt++;
        }
        //모든 파이러스가 퍼진 경우라면 걸린 시간(cnt)를 최소값으로 갱신
        if(checkZc == zeroCnt){
            ret = min(cnt, ret);
        }
    } while (next_permutation(vArr.begin(), vArr.end()));
 
    if(ret == INT_MAX)
        cout << "-1" <<"\n";
    else
        cout << ret << "\n";
}