백준 17142 연구소3
https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고
www.acmicpc.net
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 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 2M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
* 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 *시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
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
* - 3 2 3 4 *연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
입력
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
예제 입력 1 복사
7 3
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
예제 출력 1 복사
4[풀이 과정]
# 변수 설명
- arr[MAX][MAX] : 주어진 연구실 상태
- Time[MAX][MAX] : 바이러스가 퍼지는 시간을 저장할 배열
- result : 연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 저장할 변수
- blank : 현재 연구소의 빈칸의 개수
- virus : 모든 바이러스의 위치를 저장할 벡터
- cur_virus : 현재 선택된 M개의 바이러스의 인덱스(virus의 인덱스)
1. 입력을 받고 바이러스의 위치와 빈칸의 개수를 저장해둔다.
2. 빈칸이 없는 경우는 더이상 진행할 필요가 없으므로 0을 출력한다.
빈칸이 있을 경우엔 activate_virus함수를 실행한다.
3. activate_virus(int idx, int x)
- M개가 선택된 경우
- spread_virus()함수를 실행시켜 바이러스가 전체 연구소에 퍼지는 시간을 구한다.
- 최종적으로 최소시간을 구해야하므로 result를 total_time과 비교해 최소값으로 업데이트해준다.
- M개가 선택되지 않은 경우
- 선택하지 않은 바이러스 중에 하나를 선택한다.
4. spread_virus()
- 선택된 바이러스들이 동시에 퍼지기 시작해야하므로 cur_virus에 있는 모든 바이러스를 q에 넣고 방문 표시한다.
- q에 더이상 값이 없을 때까지 탐색을 진행한다.
- 현재 위치에서 상하좌우로 이동하면서 경계를 넘지 않고 벽이 아닌 경우엔 방문 표시하고 이전 시간 + 1을 해주며
또 다른 탐색을 위해 q에 넣는다.
- 연구실 전체를 탐색하며 빈칸이었던 곳 중에 시간이 0인 곳은 바이러스가 퍼지지 못한 곳이므로 INF 값을 리턴한다.
- 나머지의 경우엔 최종 걸린 시간을 구하기 위해 max함수로 비교해 res를 구한다.
- res를 리턴한다.
5. 최종적으로 result가 INF인 경우는 한 번도 연구실 전체에 바이러스가 퍼진 적이 없는 것이기 때문에 -1을 출력하고 나머지의 경우엔 최소 시간인 result를 출력한다.
[소스 코드]
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 55;
const int INF = 987987987;
int N, M, arr[MAX][MAX], Time[MAX][MAX], result = INF, blank;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool use[15], visited[MAX][MAX];
vector <pair<int, int>> virus;
vector <int> cur_virus;
int spread_virus(){
memset(Time, 0, sizeof(Time));
memset(visited, 0, sizeof(visited));
queue <pair<int,int>> q;
for(int i=0;i<cur_virus.size();i++) {
int idx = cur_virus[i];
int x = virus[idx].first;
int y = virus[idx].second;
q.push({x, y});
visited[x][y] = true;
}
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N || arr[nx][ny] == 1) continue;
if(!visited[nx][ny]){
visited[nx][ny] = true;
Time[nx][ny] = Time[x][y]+1;
q.push({nx, ny});
}
}
}
int res = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(arr[i][j] == 0){
if(Time[i][j] == 0) return INF;
else res = max(res, Time[i][j]);
}
}
}
return res;
}
void activate_virus(int idx, int x){
if(idx >= M){
int total_time = spread_virus();
result = min(result, total_time);
}
else{
for(int i=x;i<virus.size();i++){
if(!use[i]){
use[i] = true;
cur_virus.push_back(i);
activate_virus(idx+1, i+1);
cur_virus.pop_back();
use[i] = false;
}
}
}
}
int main(){
scanf("%d %d", &N, &M);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
scanf("%d", &arr[i][j]);
if(arr[i][j] == 2) virus.push_back({i, j});
else if(arr[i][j] == 0) blank++;
}
}
if(blank == 0) printf("0\n");
else {
activate_virus(0, 0);
if(result == INF) result = -1;
printf("%d\n", result);
}
return 0;
}