https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
n과 m이 최대 8이고 벽은 딱 3개만 세우면 되므로 시간 안에 완전 탐색을 해서 해결할 수 있다.
빈칸에 벽 3개를 세우는 모든 경우를 구해주고 3개를 정할 때마다 BFS로 바이러스를 퍼뜨려서 최대 안전영역의 수를 구해주면 된다. 즉 전형적인 완전 탐색 + BFS 문제이다.
안전 영역의 수는 0인 곳의 수를 미리 cnt 변수에 저장해 두고 바이러스가 퍼질 때마다 cnt에서 1씩 감소시켰다.
어렵지 않으므로 자세한 설명은 코드 주석 참고!
|
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
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, m, ans;
int map[9][9];
bool check[9][9];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs() {
queue<pair<int, int>> q;
memset(check, false, sizeof(check));
//안전역역의 수
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//안전영역이면 cnt증가
if (map[i][j] == 0) {
cnt++;
} else if (map[i][j] == 2) {
//바이러스이면 큐에 넣어준다.
q.push(make_pair(i, j));
check[i][j] = true;
}
}
}
int x, y;
//바이러스를 퍼뜨린다.
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
//범위 체크
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
//벽
if (map[nx][ny] == 1) continue;
//방문 체크
if (check[nx][ny]) continue;
//(nx,ny)로 바이러스 확산
q.push(make_pair(nx, ny));
check[nx][ny] = true;
//안전영역의 수가 감소한다.
cnt--;
}
}
//안전영역의 수를 리턴
return cnt;
}
void solve(int cnt) {
//벽 3개를 세웠다.
if (cnt == 3) {
int tmp = bfs();
//안전영역의 최댓값을 저장
if (ans < tmp) ans = tmp;
return;
}
//벽을 세우는 모든 경우를 구해준다.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// (i,j)가 빈칸이면 벽을 세워준다.
if (map[i][j] == 0) {
map[i][j] = 1;
solve(cnt + 1);
map[i][j] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
solve(0);
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 14499. 주사위 굴리기 (0) | 2019.08.04 |
|---|---|
| [BOJ] 14503. 로봇 청소기 (0) | 2019.08.04 |
| [BOJ] 15685. 드래곤 커브 (0) | 2019.08.04 |
| [BOJ] 15686. 치킨 배달 (0) | 2019.08.04 |
| [BOJ] 16234. 인구 이동 (0) | 2019.08.02 |