(백준 c++)17141 연구소2

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

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

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

 

전역 변수가 생각보다 많다.

차근차근 알아가 보자..!

 

cnt는 맵에 바이러스를 놓을 수 있는 공간의 총 개수이다.

N과 M은 각각 맵의 크기와 바이러스를 놓는 개수.

answer은 정답을 리턴하는 변수.

max_virus는 맵에서 벽(1)을 제외한 나머지 공간에 바이러스가 전파되는 개수이다. 즉, N * N - (1의 개수)이다.

bool check[10]은 경우의 수를 세기 위해 모든 조합을 찾아낼 때 사용한다.

int arr[10]은 cnt개 중 M개를 뽑았을 때 차례대로 저장하는 배열이다.

int board[50][50]은 맵.

visited는 bfs를 할 때 탐색 여부를 확인하는 변수이다. bfs를 할 때 visited를 복사하여 검사한다.

combination은 바이러스를 놓을 위치를 저장하는 벡터다. cnt개 중 M개를 뽑았을 때 바이러스의 좌표를 저장한다.

v는 맵에서 바이러스를 심을 수 있는 위치를 나타내는 좌표가 저장된다.

 

우선 main에서 N, M을 받아오고, 맵의 정보를 저장한다.

이 때 0, 1, 2 여부를 확인해서 해당 좌표가 1이면 visited[i][j] = true로 바꿔 벽이라고 암시한다.

해당 좌표가 1이 아니고 2라면 바이러스를 놓을 수 있는 공간이므로 cnt++, v에 좌표를 넣어준 후 max_virus++를 해준다.

해당 좌표가 1이 아니고 0이라면 그냥 max_virus++만 해준다.

 

이제 dfs를 통해 바이러스를 놓을 수 있는 모든 조합을 찾아본다.

아래 링크에 조합 관련 문제가 있으니 참고..!

eunchanee.tistory.com/118?category=1129978

(백준 c++) 15650 N과 M(2)

M개에 맞게 조합을 찾았으면 해당 좌표들을 bfs를 통해 최단 시간을 찾아내면 된다.

좌표 값들을 큐에 넣어주고, 방문 여부의 복사본을 생성한다.

virus 변수는 현재 바이러스의 개수를 나타낸다.

time은 최단 시간을 나타내는데, 처음에는 -1이다.

왜냐하면 처음 바이러스를 놓을 때는 시간이 카운팅 되면 안되기 때문이다.

 

큐가 비어지게 되면 max_virus와 virus를 비교해 동일한지 검사한다.

동일하면 answer와 time 중 작은 값을 answer에 저장하면 된다.

만약 answer == 9999라면 바이러스를 퍼트릴 수 없는 경우이므로 -1을 출력.

그 외에는 answer를 출력하면 된다.

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

using namespace std;

int cnt = 0;
int N = 0;
int M = 0;
int answer = 9999;
int max_virus = 0;
bool check[10] = {false, };
int arr[10] = {0, };
int board[50][50];
vector<vector<bool>> visited(50, vector<bool>(50, false));
vector<int> combination;
vector<pair<int, int>> v;

void dfs(int, int);
void bfs();

void dfs(int start, int count){
    if(count == M){
        for(int i = 0; i < M; i++){
            combination.push_back(arr[i]);
        }
        bfs();
        return;
    }

    for(int i = start; i < cnt; i++){
        if(!check[i]){
            check[i] = true;
            arr[count] = i;
            dfs(i + 1, count + 1);
            check[i] = false;
        }
    }
}

void bfs(){
    queue<pair<int, int>> q;
    vector<vector<bool>> tmp = visited;
    int time = -1, virus = 0;

    for(int i = 0; i < M; i++){
        q.push(v[arr[i]]);
        tmp[v[arr[i]].first][v[arr[i]].second] = true;
        virus++;
    }

    while(!q.empty()){
        int size = q.size();

        for(int i = 0; i < size; i++){
	        int x = q.front().first;
	        int y = q.front().second;
	        q.pop();
            if(x - 1 >= 0 && !tmp[x - 1][y]){
                q.push(make_pair(x - 1, y));
                tmp[x - 1][y] = true;
                virus++;
            }
            if(y + 1 < N && !tmp[x][y + 1]){
                q.push(make_pair(x, y + 1));
                tmp[x][y + 1] = true;
                virus++;
            }
            if(x + 1 < N && !tmp[x + 1][y]){
                q.push(make_pair(x + 1, y));
                tmp[x + 1][y] = true;
                virus++;
            }
            if(y - 1 >= 0 && !tmp[x][y - 1]){
                q.push(make_pair(x, y - 1));
                tmp[x][y - 1] = true;
                virus++;
            }
        }
        time++;
    }
    
    if(virus == max_virus){
        answer = answer < time ? answer : time;
    }
}

int main(void){
    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] != 1){
                if(board[i][j] == 2){
                cnt++;
                v.push_back(make_pair(i, j));
                }
                max_virus++;
            }
            else{
                visited[i][j] = true;
            }
        }
    }

    dfs(0, 0);

	if(answer == 9999){
		cout << -1;
	}
	else{
		cout << answer;	
	}
    return 0;
}