https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는
www.acmicpc.net
주어진 배열에 있는 바이러스들 중 m개를 골라 활성화시켜서 연구소에 퍼뜨리는 문제이다.
m개를 고르는 모든 경우를 해보고, 골랐을 때마다 bfs로 바이러스를 퍼뜨려서
모두 퍼뜨리는데 걸리는 최소시간을 구하면 된다. 즉 완전 탐색 + bfs 문제이다.
이 문제에서 주의 할점은 처음에 활성화하지 않은 바이러스들이다.
이 바이러스들은 애초에 퍼져있는 상태나 마찬가지이므로 이 위치는 0초에 퍼져있는 상태나 마찬가지이다.
그래서 처음에 시간을 0으로 처리해줬다가 bfs부분에서 넘어가 버려서 다음과 같은 테스트 케이스에서 -1이 나왔다.
(원래 정답은 2가 나와야 함)
4 2
0110
2112
2112
0110
활성화하지 않은 바이러스를 벽처럼 여겨서 넘어가지 못했기 때문이다.
그래서 일단 얘네들도 빈칸처럼 똑같이 처리해줬다.
그리고 마지막에 모두 퍼뜨리는데 걸리는 시간을 구할 때 좌표의 값이 2라면(바이러스였다면) 최대 시간으로 간주하지 않는다.
밑의 코드에서는 0인 경우(원래 빈칸이었던 경우)에만 최대 시간을 계산해주었다.
|
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int map[50][50];
int time[50][50];
int ans;
vector<pair<int, int>> virus;
vector<pair<int, int>> alive;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int check() {
int maxtime = 0;
//모든 칸을 검사
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//처음에 활성화하지 않은 바이러스의 시간을 최대값으로 저장하면 안되므로
//현재 칸이 원래 빈칸이었고(바이러스가 아니고)
// 최대시간보다 더 긴 시간을 가지고 있으면 최대시간으로 저장
if (map[i][j] == 0 && maxtime < time[i][j]) {
maxtime = time[i][j];
}
//빈칸인데 시간이 저장되어 있지 않다(바이러스가 퍼지지 못했다)
if (map[i][j] == 0 && time[i][j] == -1) {
return -1;
}
}
}
//모두 걸리는데 걸리는 시간을 리턴
return maxtime;
}
void bfs() {
memset(time, -1, sizeof(time));
queue<pair<int, int>> q;
int x, y;
//활성 바이러스들을 큐에 넣어준다.
for (int i = 0; i < m; i++) {
x = alive.at(i).first;
y = alive.at(i).second;
q.push(make_pair(x, y));
time[x][y] = 0;
}
int nx, ny;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
//인접한 네방향으로 퍼진다.
for (int k = 0; k < 4; k++) {
nx = x + dx[k];
ny = y + dy[k];
//범위 체크
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
//벽인 경우
if (map[nx][ny] == 1) continue;
//빈 칸에 이미 방문
if (time[nx][ny] != -1) continue;
q.push(make_pair(nx, ny));
time[nx][ny] = time[x][y] + 1;
}
}
//check함수로 모두 퍼질 수 없는 경우인 경우 -1, 그렇지 않은 경우 모두 퍼지는데
//걸리는 시간을 받아온다.
int tmp = check();
if (tmp == -1) {
//초기값이라면 -1을 그대로 넣어준다.
if (ans == 10000000) {
ans = -1;
}
}
else {
//받아온 시간이 최솟값이라면 ans에 저장
//ans가 -1인 경우에도 새로 받아온 값(가능한 경우)로 바꿔줄 수 있다.
if (ans == -1 || ans > tmp) {
ans = tmp;
}
}
}
//활성화 시킬 바이러스 m개를 고른다.
void select(int index, int cnt) {
//m개를 고른 경우
if (cnt == m) {
//바이러스를 활성화 시킨다.
bfs();
return;
}
//고를 수 있는 경우를 모두 넘어간 경우 리턴
if (index >= virus.size()) return;
//index번째 바이러스의 좌표를 가져온다.
int x = virus.at(index).first;
int y = virus.at(index).second;
//index번째 바이러스를 선택한다.
alive.push_back(make_pair(x, y));
select(index + 1, cnt + 1);
//index번째 바이러스를 선택하지 않는 경우
alive.pop_back(); //선택하는 경우에서 넣은 거 뺀다
select(index + 1, cnt);
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
//바이러스인 경우 벡터에 좌표를 저장
if (map[i][j] == 2) virus.push_back(make_pair(i, j));
}
}
//최솟값을 찾기 위해서 큰 값을 넣어둔다.
ans = 10000000;
select(0, 0);
cout << ans << '\n';
//선택하지 않은 바이러스 부분에도 시간 넣어줘야한다!!!!
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17144. 미세먼지 안녕! (0) | 2019.07.30 |
|---|---|
| [BOJ] 17140. 이차원 배열과 연산 (0) | 2019.07.30 |
| [BOJ] 1806. 부분합 (0) | 2019.07.16 |
| [BOJ] 2003. 수들의 합 2 (0) | 2019.07.15 |
| [BOJ] 2748. 피보나치 수 2 (0) | 2019.07.15 |