(백준 c++)17142 연구소3

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

완전탐색과 BFS를 활용.

 

변수 설명)

N = 맵의 크기

M = 활성 상태로 바꿀 수 있는 바이러스의 수

answer = 답

totalVirus = 바이러스를 놓을 수 있는 수(2의 개수)

directX, directY = 상하좌우로 움직이기 위해 사용하는 배열

check = 모든 칸에 바이러스를 놓을 수 있는지 확인하기 위한 bool 변수

space = 0의 개수(빈 칸의 개수)

board = 연구소 맵 벡터

virus = 바이러스가 위치한 좌표(2의 좌표)

ind = next_permutation() 함수(조합)를 사용하기 위한 벡터

 

우선 N * N 크기만큼 맵의 정보를 받아오자.

그리고 board[i][j]가 2라면 virus 벡터에 좌표를 넣어주고, totalVirus++.

0이라면 space를 늘려주어 빈 칸을 카운팅 해주자.

 

totalVirus 중 M개의 바이러스를 활성 상태로 바꾸기 위해 ind를 활용한다.

조합에 관한 설명은 아래 블로그를 참고!

twpower.github.io/90-combination-by-using-next_permutation

[Algorithm] C++에서 next_permutation을 이용해 조합(Combination) 구하기

 

이제 do~while문으로 모든 경우를 탐색하자.

time = 바이러스가 모두 퍼진 시간

tmpSpace = BFS를 돌 때마다 바이러스가 모두 퍼졌는지 확인하기 위한 임시 변수

activeVirus = 활성 상태가 된 바이러스의 위치 좌표 큐

tmpBoard = BFS를 돌 때 임시로 사용하는 board

tmpVisited = BFS를 돌 때 임시로 사용하는 visited

 

ind 벡터를 모두 돌면서 현재 위치가 1이면 virus[i]에 있는 위치 좌표를 activeVirus에 넣어준다.

activeVirus가 빌 때까지 반복.

전형적인 BFS를 사용하면 된다.

 

현재 큐에 담겨있는 크기만큼 반복하고, 끝나면 time++을 해준다.

만약 tmpSpace가 0이라면 바이러스가 모두 퍼진 상태이므로 break로 while문을 탈출한다.

 

nx, ny는 상하좌우를 나타내는 좌표로,

이 좌표가 0 ~ N 사이이고, 방문하지 않은 좌표라면 조건 검사를 추가로 해준다.

 

tmpBoard[nx][ny]가 0이라면

빈 칸이므로 바이러스가 퍼진다.

activeVirus에 이 좌표를 push.

tmpVisited = true로 바꿔주고, tmpSpace--를 해주어 카운팅을 해준다.

 

tmpBoard[nx][ny]가 1이면 벽이므로 아무것도 해주지 않는다.

 

tmpBoard[nx][ny]가 2라면 비활성 바이러스를 뜻한다.(tmpVisited[nx][ny]가 false이기 때문에 비활성 바이러스)

activeVirus에 push.

tmpVisited = true로 바꿔준다.

 

while문이 끝나고 tmpSpace를 확인한다.

0이라면 바이러스가 모두 퍼진 상태, answer과 time을 비교하여 더 작은 쪽을 answer에 넣어준다.

그리고 check = true로 바꿔주어 한 번이라도 바이러스가 모두 퍼졌다는 상태로 만들어준다.

만약 check = false라면 한번도 바이러스가 모두 퍼진 적이 없다는 뜻이다.

 

모든 경우를 탐색하고 check의 상태를 확인하여

false 인 경우 -1 출력.

true 인 경우 answer을 출력하면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(void){
    int N, M, answer = 9999, totalVirus = 0;
    int directX[4] = {-1, 1, 0, 0};
    int directY[4] = {0, 0, -1, 1};
    bool check = false;
    int space = 0;

    cin >> N >> M;

    vector<vector<int>> board(N, vector<int>(N, 0));
    vector<pair<int, int>> virus;
    vector<int> ind(M, 1);

    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});
                totalVirus++;
            }
            else if(board[i][j] == 0){
                space++;
            }
        }
    }

    for(int i = M; i < totalVirus; i++){
        ind.push_back(0);
    }

    sort(ind.begin(), ind.end());

    do{
        int time = 0;
        int tmpSpace = space;
        queue<pair<int, int>> activeVirus;
        vector<vector<int>> tmpBoard = board;
        vector<vector<bool>> tmpVisited(N, vector<bool>(N, false));

        for(int i = 0; i < ind.size(); i++){
            if(ind[i]){
                //활성 바이러스
                activeVirus.push(virus[i]);
                tmpVisited[virus[i].first][virus[i].second] = true;
            }
        }

        while(!activeVirus.empty()){
        	if(!tmpSpace){
        		break;
        	}
        	
            int size = activeVirus.size();

            for(int i = 0; i < size; i++){
                int x = activeVirus.front().first;
                int y = activeVirus.front().second;

                activeVirus.pop();

                for(int j = 0; j < 4; j++){
                    int nx = x + directX[j];
                    int ny = y + directY[j];

                    if(nx >= 0 && nx < N && ny >= 0 && ny < N  && !tmpVisited[nx][ny]){
                        if(tmpBoard[nx][ny] == 0){
                            activeVirus.push({nx, ny});
                            tmpVisited[nx][ny] = true;
                            tmpSpace--;
                        }
                        else if(tmpBoard[nx][ny] == 2 && tmpSpace > 0){
                            activeVirus.push({nx, ny});
                            tmpVisited[nx][ny] = true;
                        }
                    }
                }
            }

            time++;
        }
        
        if(!tmpSpace){
            answer = answer < time ? answer : time;
            check = true;
        }
    }while(next_permutation(ind.begin(), ind.end()));

    if(!check){
        cout << -1;
    }
    else{
        cout << answer;
    }

    return 0;
}