백준 14502. 연구소
알고리즘 중급 문제 중 611 - BFS(연습)
1. 간단 설명
N * M 인 연구소 맵
0은 빈칸, 1은 벽, 2는 바이러스
바이러스는 상하좌우 인접한 빈 칸으로 퍼져나간다
격벽을 3개 세워서 바이러스를 차단해서, 얻을 수 있는 안전 영역의 최대 크기를 구하는 문제
2. 예제
1
2
3
4
5
6
7
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 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
1
2
3
4
5
6
7
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
다음과 같이 벽을 세우면
1
2
3
4
5
6
7
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
다음과 같이 바이러스가 퍼지게 되고, 안전 영역은 27만큼 얻을 수 있다
3. 알고리즘
가장 먼저 떠오르는 방법은
N*M 에서 0인 부분에 차례대로 3부분을 선택하여 맵을 생성한뒤
이를 BFS를 돌려 안전구역의 크기를 계산하는 방법인데,
이게 시간 내에 가능할지 궁금했다
N, M의 크기가 최대값인 8인 경우,
1
2
3
4
5
6
7
8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2
다음과 같은 예시가 있다면,
63C3 = (63 * 62 * 61) / (3 * 2 * 1) = 41664 경우의 수의 BFS를 구해야한다
BFS를 구하는데 걸리는 시간은 O(V+E)이므로,
V = 64, E = 4V = 4 * 64 = 256
각 BFS 시간 복잡도는 O(320)정도이므로,
총 시간 복잡도는 320 * 41664 = 2,666,496 정도 걸리는 것을 알 수 있다.
충분히 2초 내로 해결 가능할듯 하다
알고리즘
1
2
3
4
5
6
7
1. 맵을 입력받는다
2. 3중 for문을 돌면서 차례대로 3곳을 선택하여 1로 수정한다
- 차례로 세곳을 선택하는 방법으로 DFS를 사용했다
3. 수정한 맵을 토대로 BFS를 돌리고, 안전구역의 크기를 계산한다
4. 구한 안전구역의 크기를 기록된 최대값과 비교하여 갱신한다
5. 맵을 원상복구한다
6. 모든 경우를 체크할 때 까지 이를 반복한다
필요 변수
int N, M(3 ≤ N, M ≤ 8)- 0은 빈칸, 1은 벽, 2는 바이러스를 기록할
int map[8][8] - 바이러스의 시작 좌표를 기록해둘 벡터
vector<pair<int,int>> virus - BFS탐색을 위한 int BFS()
- 4방향 탐색
int direct[4][2] - BFS 탐색용 큐
queue<pair<int, int>> qu - 방문체크용 맵은 별도로 사용하지 않고, 맵에 그대로 기록하는 방법을 사용함
- 4방향 탐색
- 최대 안전구역의 크기
int max_safehouse_size
4. 소스코드
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
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX 8
using namespace std;
int N, M;
int map[MAX][MAX];
int backup[MAX][MAX];
int max_safehouse_size = 0;
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct node {
int y;
int x;
};
vector<node> virus;
vector<node> wall;
void Input() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
cin >> map[y][x];
// 바이러스인 경우 기록해둠
if (map[y][x] == 2) {
virus.push_back({ y, x });
}
}
}
}
int BFS() {
queue<node> qu;
// 모든 바이러스 시작점을 큐에 넣음
for (node e : virus) {
qu.push(e);
}
while (!qu.empty()) {
node now = qu.front();
qu.pop();
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dy >= N || dx < 0 || dx >= M) continue; // 맵 밖으로 벗어난 경우
if (map[dy][dx] != 0) continue; // 빈칸이 아닌경우 (이미 바이러스가 있거나, 벽)
map[dy][dx] = 2;
qu.push({ dy, dx });
}
}
int size = 0;
for (int yy = 0; yy < N; yy++) {
for (int xx = 0; xx < M; xx++) {
if (map[yy][xx] == 0) {
size++;
}
}
}
return size;
}
void DFS(int level) {
// 3개 고른 경우
if (level == 3) {
memcpy(backup, map, sizeof(map)); // BFS 수행중 원본이 손상되므로, 백업해둠
max_safehouse_size = max(max_safehouse_size, BFS());
memcpy(map, backup, sizeof(map)); // 복원
return;
}
for (int yy = 0; yy < N; yy++) {
for (int xx = 0; xx < M; xx++) {
if (map[yy][xx] == 0) {
wall.push_back({ yy, xx });
map[yy][xx] = 1;
DFS(level + 1);
wall.pop_back();
map[yy][xx] = 0;
}
}
}
}
int main() {
Input();
// 빈칸중 3칸을 고른다
DFS(0);
cout << max_safehouse_size;
BFS();
return 0;
}
2차원 배열을 백업하고, 복원하는데 사용하였다
또한, DFS에서 직접 탐색하며 빈칸을 찾는 방법을 사용하였는데
빈칸을 미리 기록해두고, 이 중 3개를 선택하는 방법을 사용하면 더 효율적으로 구할 수 있을 것 같다
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.