[URL]
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
[풀이 과정]
* 재귀, DFS, BFS
1. 재귀 DFS로 3개의 벽 선정
2. 3개 벽 세워 두고 바이러스(map[][] == 2)인 부분 BFS로 퍼뜨림
3. 가능 갯수 카운팅 후 최대값 출력
[소스 코드]
|
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
struct info {
int x;
int y;
};
vector <info> v;
vector <info> virus;
queue <info> q;
int N, M;
int map[10][10];
int c_map[10][10];
bool check[100] = { 0, }; // DFS 빈칸 후보 벡터 중 3개 뽑을 때 쓰는 check[] 배열
bool visited[10][10] = { 0, }; // BFS 색칠하기 위해 방문여부 확인배열
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int wallCand[3];
int cand[987654];
int candCnt = 0;
void init() {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 0)
{
info temp;
temp.x = i;
temp.y = j;
v.push_back(temp);
}
if (map[i][j] == 2)
{
info temp;
temp.x = i;
temp.y = j;
virus.push_back(temp);
}
}
}
}
void copyMap() {
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
c_map[i][j] = map[i][j];
}
}
}
void bfs(int index)
{
info temp;
temp.x = virus[index].x;
temp.y = virus[index].y;
q.push(temp);
while (!q.empty())
{
int cx = q.front().x;
int cy = q.front().y;
visited[cx][cy] = true;
q.pop();
for (int k = 0; k < 4; k++)
{
int nx = cx + dx[k];
int ny = cy + dy[k];
if (nx >= 0 && ny >= 0 && nx < N && ny < M)
{
if (visited[nx][ny] == false && c_map[nx][ny] == 0)
{
visited[nx][ny] = true;
c_map[nx][ny] = 2;
info temp;
temp.x = nx;
temp.y = ny;
q.push(temp);
}
}
}
}
}
int go() {
int goRes = 0;
//-- 초기화 시작 -------------------
copyMap();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
visited[i][j] = false;
}
}
//------------------- 초기화 끝 ----
for (int i = 0; i < 3; i++)
{
c_map[v[wallCand[i]].x][v[wallCand[i]].y] = 1;
}
for (int i = 0; i < virus.size(); i++)
{
bfs(i);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (c_map[i][j] == 0)
{
goRes++;
}
}
}
return goRes;
}
void dfs(int cnt) {
if (cnt == 3)
{
cand[candCnt++] = go();
return;
}
for (int i = cnt; i < v.size(); i++)
{
if (cnt == 0)
{
if (check[cnt] == false)
{
check[cnt] = true;
wallCand[cnt] = i;
cnt++;
dfs(cnt);
cnt--;
check[cnt] = false;
}
}
else
{
if (check[cnt] == false && i > wallCand[cnt - 1])
{
check[cnt] = true;
wallCand[cnt] = i;
cnt++;
dfs(cnt);
cnt--;
check[cnt] = false;
}
}
}
}
int main() {
init();
dfs(0);
int Max = -1;
for (int i = 0; i < candCnt; i++)
{
if (cand[i] >= Max)
Max = cand[i];
}
printf("%d\n", Max);
return 0;
}
|
cs |
'Algorithm > 백준' 카테고리의 다른 글
| [BOJ] - 14499. 주사위 굴리기 (0) | 2019.04.11 |
|---|---|
| [BOJ] - 14500. 테트로미노 (0) | 2019.04.11 |
| [BOJ] - 2667. 단지번호붙이기 (0) | 2019.04.09 |
| [BOJ] - 14888. 연산자 끼워넣기 (0) | 2019.04.09 |
| [BOJ] - 14889. 스타트와 링크 (0) | 2019.04.09 |