💡 너비 우선 탐색/브루트포스 알고리즘/그래프 이론/그래프 탐색
Memory 2036KB Time 16ms Code Length 3067B
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
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
// M개를 활성 상태로 변경하려고함 => dfs로 활성화 할 바이러스 선택
// 0 빈칸, 1은 벽, 2는 바이러스
// 활성화된 바이러스가 비활성 바이러스 칸으로 이동시 활성으로 변함. => 사실상 상관없음. 바이러스가 이미 퍼져있는걸로 인정.
// 최소시간 구하기. 바이러스를 전부 퍼트릴 수 없다면 -1 반환.
int N, M;
int map[50][50];
char spread_map[50][50];
int choosedVirus[10] = {};
int result = -1;
struct info {
int y, x;
};
vector <info> vc;
void init() {
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) {
vc.push_back({ i,j });
}
}
}
}
bool findEmpty() { // 빈공간 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (spread_map[i][j] == '#') { // 빈공간이 있는경우
return true;
}
}
}
return false;
}
int findMax(int visited[50][50]) { // 최댓값 찾기
int Max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (spread_map[i][j] == '*') continue;
if (visited[i][j] > Max) {
Max = visited[i][j];
}
}
}
return Max-1; // visited[][]가 1부터 시작하므로 -1을 해줌.
}
int spreadVirus() {
int visited[50][50] = {0};
memset(spread_map,0,sizeof(spread_map));
queue<info> q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) {
spread_map[i][j] = '#'; // 빈칸 처리
}
else if (map[i][j] == 1) {
spread_map[i][j] = '-'; // 벽
}
else if (map[i][j] == 2) {
spread_map[i][j] = '*'; // 비활성화 바이러스
}
}
}
for (int i = 0; i < vc.size(); i++) {
if (choosedVirus[i] == 1) { // 활성화된 바이러스 표시
spread_map[vc[i].y][vc[i].x] = '0'; // 활성화 바이러스
q.push({ vc[i].y, vc[i].x });
visited[vc[i].y][vc[i].x] = 1;
}
}
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
while (!q.empty()) {
info now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (visited[ny][nx] != 0) continue;
if (spread_map[ny][nx] == '-') continue;
else if (spread_map[ny][nx] == '#') {
spread_map[ny][nx] = '0';
}
visited[ny][nx] = visited[now.y][now.x] + 1;
q.push({ ny,nx });
}
}
if (!findEmpty()) { // 빈공간이 없을때
return findMax(visited);
}
return -1;
}
void chooseVirus(int depth, int now) {
if (depth == M) {
int tmp = spreadVirus();
if (tmp == -1) return; // 결과가 -1인 경우는 생각 X
if (result == -1) result = tmp;
else if (result > tmp){
result = tmp;
}
return;
}
for (int i = now; i < vc.size(); i++) {
if (choosedVirus[i] == 1) continue;
choosedVirus[i] = 1;
chooseVirus(depth + 1, i+1);
choosedVirus[i] = 0;
}
}
int main() {
init();
chooseVirus(0, 0);
cout << result << endl;
return 0;
}
이 코드는 주어진 지도에서 바이러스를 활성화하여 최소 시간 안에 모든 빈 칸을 감염시키는 문제를 해결하는 프로그램이다.
먼저, 초기화 함수(init)에서는 지도의 크기와 바이러스의 위치를 입력받는다.
그 후, 활성화된 바이러스가 주변의 비활성 바이러스 칸으로 이동하면 활성 상태로 변하는데, 이는 코드에서는 이미 바이러스가 퍼져있는 것으로 처리한다.
바이러스를 전부 퍼트릴 수 없는 경우에는 -1을 반환한다.
주요 함수로는 spreadVirus 함수가 있는데, 이 함수는 바이러스를 퍼뜨리는 역할을 한다.
바이러스를 활성화할 바이러스를 선택하는 chooseVirus 함수를 통해 모든 가능한 바이러스 조합을 탐색하고, 최종적으로 최소 시간을 출력한다.
처음 코드를 작성했을 때, 시간초과가 매우 많이 발생했다… 테스트 케이스는 대부분 맞았지만, 시간초과가 발생이 일어났다.
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
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
// M개를 활성 상태로 변경하려고함 => dfs로 활성화 할 바이러스 선택
// 0 빈칸, 1은 벽, 2는 바이러스
// 활성화된 바이러스가 비활성 바이러스 칸으로 이동시 활성으로 변함. => 사실상 상관없음. 바이러스가 이미 퍼져있는걸로 인정.
// 최소시간 구하기. 바이러스를 전부 퍼트릴 수 없다면 -1 반환.
int N, M;
int map[50][50];
char spread_map[50][50];
int choosedVirus[10] = {};
int result = -1;
struct info {
int y, x;
};
vector <info> vc;
void init() {
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) {
vc.push_back({ i,j });
}
}
}
}
bool findEmpty() { // 빈공간 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (spread_map[i][j] == '#') { // 빈공간이 있는경우
return true;
}
}
}
return false;
}
int findMax(int visited[50][50]) { // 최댓값 찾기
int Max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] > Max) {
Max = visited[i][j];
}
}
}
return Max-1; // visited[][]가 1부터 시작하므로 -1을 해줌.
}
int spreadVirus() {
int visited[50][50] = {0};
memset(spread_map,0,sizeof(spread_map));
queue<info> q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) {
spread_map[i][j] = '#'; // 빈칸 처리
}
else if (map[i][j] == 1) {
spread_map[i][j] = '-'; // 벽
}
else if (map[i][j] == 2) {
spread_map[i][j] = '*'; // 비활성화 바이러스
}
}
}
for (int i = 0; i < vc.size(); i++) {
if (choosedVirus[i] == 1) { // 활성화된 바이러스 표시
spread_map[vc[i].y][vc[i].x] = '0'; // 활성화 바이러스
q.push({ vc[i].y, vc[i].x });
visited[vc[i].y][vc[i].x] = 1;
}
}
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
while (!q.empty()) {
info now = q.front(); q.pop();
if (!findEmpty()) { // 빈공간이 없을때
return findMax(visited);
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (visited[ny][nx] != 0) continue;
if (spread_map[ny][nx] == '-') continue;
else if (spread_map[ny][nx] == '#' || spread_map[ny][nx] == '*') {
spread_map[ny][nx] = '0';
}
visited[ny][nx] = visited[now.y][now.x] + 1;
q.push({ ny,nx });
}
}
return -1;
}
void chooseVirus(int depth) {
if (depth == M) {
int tmp = spreadVirus();
if (tmp == -1) return; // 결과가 -1인 경우는 생각 X
if (result == -1) result = tmp;
else if (result > tmp){
result = tmp;
}
return;
}
for (int i = 0; i < vc.size(); i++) {
if (choosedVirus[i] == 1) continue;
choosedVirus[i] = 1;
chooseVirus(depth + 1);
choosedVirus[i] = 0;
}
}
int main() {
init();
chooseVirus(0);
cout << result << endl;
return 0;
}
문제의 원인은 두 가지 였다.
첫 번째, 조합을 코딩했다고 생각했는데, 순열을 코딩했기 때문이다. 그래서 매개변수를 추가하여 재귀 함수로 들어오기 전 인덱스 보다 더 이후의 인덱스부터 선택을 하게 끔 하여 경우의 수를 줄였다.
두번째, dfs로 조합을 선택한 이후 bfs를 돌려야 되는데 if문으로 바이러스가 다 확산 됐는 지 확인을 하고 확산되었다면 리턴, 결국 while문을 다 돌고 빠져나오면 -1을 반환하는 식으로 코딩을 했다.
이 때문에 다 확산 됐는지 확인하는 작업을 q의 원소마다 진행하게 되었기에 최대 2500배에 달하는 작업이 수행되었다. 그렇기에 채우는 작업을 모두 진행 후, 확산 되었는지 확인 작업은 한번만 해주었다.
이때, “활성화된 바이러스가 비활성 바이러스 칸으로 이동 시 활성으로 변함” 이 부분 때문에 활성화 바이러스가 비활성 바이러스 지점에 도달하면서 끝나버리면 바이러스가 퍼지는데 걸리는 최소시간이 1 더 늘어나게 되었다. 이를 해결하기 위해서 최댓값을 체크할 때 만약 해당 칸이 비활성 바이러스가 있던 칸이었다면 최댓값 계산에서 제외 하는 방식으로 하였다.
