알고리즘 문제풀이/백준
[백준 17142번] 연구소 3
슥지니
2022. 3. 30. 15:31
반응형
문제 링크: https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고
www.acmicpc.net
<문제 풀이> 조합, BFS
이 문제는 두 가지만 조심하면 되는데
첫 번째는 "활성 바이러스로 인해 비활성 바이러스가 활성 바이러스로 바뀔 때 0초가 걸린다"입니다.
이 경우에는 활성 바이러스를 기준으로 BFS를 하다가 비활성 바이러스를 만나면 따로 바이러스라고 체크해주고 나중에 걸린 시간을 갱신할 때 이 부분은 스킵하면 됩니다.
두 번째는 조합 알고리즘입니다.
10Cm의 조합 알고리즘을 작성해야 하는데 실수로 틀린 알고리즘을 작성해서 시간이 더 오래 걸릴 수도 있습니다.
아래 문제를 풀어보시면 도움이 됩니다.
[조합 문제]
https://www.acmicpc.net/problem/15663
15663번: N과 M (9)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
<C++ 소스 코드>
|
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
|
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
using namespace std;
#define WALL 1
#define VIRUS 2
#define ACTIVE 0
#define INACTIVE -1
#define EMPTY -2
#define INIT 99999999
#define X first
#define Y second
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
int N, M;
int board[50][50];
int visited[50][50];
bool existVirus[50][50];
vector<pair<int, int> > virus;
int virus_size;
pair<int, int> selected[10];
bool isCheck[10];
int res = -1;
int emptyCnt;
int solve(int idx, int depth) {
int ret = INIT;
if (depth == M) {
fill(&visited[0][0], &visited[49][50], EMPTY);
fill(&existVirus[0][0], &existVirus[49][50], false);
queue<pair<int, int> > Q;
for (int i = 0; i < M; i++) {
auto e = selected[i];
visited[e.X][e.Y] = ACTIVE;
Q.push({ e.X, e.Y });
}
for (auto e : virus) {
if (visited[e.X][e.Y] == EMPTY) visited[e.X][e.Y] = INACTIVE;
}
int cnt = 0;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
if (board[nx][ny] == WALL) continue;
if (visited[nx][ny] == EMPTY) {
Q.push({ nx, ny });
visited[nx][ny] = visited[cur.X][cur.Y] + 1;
}
else if (visited[nx][ny] == INACTIVE) {
existVirus[nx][ny] = true;
Q.push({ nx, ny });
visited[nx][ny] = visited[cur.X][cur.Y] + 1;
}
}
}
int temp = -1;
bool flag = false;
for (int i = 0; i < N; i++) {
if (flag) break;
for (int j = 0; j < N; j++) {
if (board[i][j] == WALL)continue;
if (existVirus[i][j] == true) continue;
if (visited[i][j] == EMPTY) {
temp = INIT;
flag = true;
break;
}
temp = max(temp, visited[i][j]);
}
}
ret = min(ret, temp);
}
else {
for (int i = idx; i < virus_size; i++) {
if (isCheck[i])continue;
selected[depth] = virus[i];
isCheck[i] = true;
ret = min(ret, solve(i + 1, depth + 1));
isCheck[i] = false;
}
}
return ret;
}
int main(void) {
ios_base::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 >> board[i][j];
if (board[i][j] == VIRUS) virus.push_back({ i, j });
else if (board[i][j] == 0)emptyCnt++;
}
}
virus_size = virus.size();
int ret = solve(0, 0);
if (ret == INIT) cout << -1;
else cout << ret;
return 0;
}
|
cs |
반응형