문제
https://www.acmicpc.net/problem/17142
문제해설
N*N 크기의 연구소가 있다.
연구소에는 빈공간인 0과 벽인 1 그리고 바이러스인 2가 존재한다.
바이러스는 활성 바이러스가 있고 비활성 바이러스가 있다.
활성 바이러스는 상하좌우 벽을 제외한 곳으로 1초마다 확산된다.
활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
N과 활성 바이러스의 개수인 M이 주어지면
모든 빈칸에 바이러스가 퍼지는 최소 시간을 구하면 된다.
바이러스를 어떻게 배치해도 모든 빈칸에 퍼지지 않는다면 -1을 출력한다.
문제풀이
일단 이 문제는 조합과 BFS가 섞인 문제이다.
조합코드로 바이러스의 위치를 정하고 그에 해당하는 BFS탐색을 해야한다.
조합은 재귀를 이용해 만들었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void virus(int cnt, int idx) {
if (cnt == m) {
...
...
bfs();
return;
}
for (int i = idx; i < vir.size(); i++) {
if (vir[i].vis == 1)
continue;
vir[i].vis = 1;
virus(++cnt, ++idx);
vir[i].vis = 0;
cnt--;
}
}
BFS 과정에서 많이 애를 먹었는데
우선 문제를 완벽히 이해하지 못해서
활성 바이러스가 비활성 바이러스를 만났을 때 어떻게 처리할지 고민이었다.
비활성 바이러스를 만났을 때 일반 빈칸처럼 시간을 +1 하게되도 틀리고
특별하게 비활성을 만나면 일반 빈칸과 같지만 시간을 그대로 가져가게해도 틀린다.
그렇다고 비활성 바이러스를 벽처럼 처리해도 틀리게 된다.
이 부분을 처리하는데 상당한 시간이 걸렸다.
최종적으로 해결한 방법은 꽤나 간단하다.
비활성 바이러스도 빈칸처럼 +1 처리를 해준뒤에
BFS 안에서 시간계산을 해주지 말고
끝나고 난 뒤에 남은 빈칸이 있는지 판단해주는 반복문 안에서
빈칸인 경우에만 시간을 계산해주면 된다.
이렇게하면 문제가 해결된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;
typedef pair<int, int>P;
int arr[51][51], visited[51][51];
int n, m, res = INT_MAX;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
struct node {
int x, y, vis;
};
vector<node>vir;
queue<P>q;
void bfs() {
while (!q.empty()) {
P now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = now.first + dx[i];
int ny = now.second + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;
if (arr[nx][ny] != 1 && visited[nx][ny] == -1) {
visited[nx][ny] = visited[now.first][now.second] + 1;
q.push({ nx,ny });
}
}
}
int time = 0;
bool flag = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0) {
if (visited[i][j] == -1) {
flag = false;
break;
}
else
time = max(time, visited[i][j]);
}
}
}
if (flag)
res = min(res, time);
}
void virus(int cnt, int idx) {
if (cnt == m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = -1;
}
}
for (int i = 0; i < vir.size(); i++) {
if (vir[i].vis == 1) {
q.push({ vir[i].x,vir[i].y });
visited[vir[i].x][vir[i].y] = 0;
}
}
bfs();
return;
}
for (int i = idx; i < vir.size(); i++) {
if (vir[i].vis == 1)
continue;
vir[i].vis = 1;
virus(++cnt, ++idx);
vir[i].vis = 0;
cnt--;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 2)
vir.push_back({ i,j,0 });
}
}
virus(0, 0);
if (res == INT_MAX)
cout << -1;
else
cout << res;
return 0;
}