14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
<풀이>
1. 연구소 지도를 입력받는다.
2. 연구소에 벽 3개를 세우고, 바이러스가 퍼졌을 때 안전 영역을 구한다.
3. 안전 영역의 최댓값을 출력한다.
<해법>
1. 연구소에 벽 3개를 세우는 방법.
=> 벽 3개를 어떻게 세워야 하는지 정할 수 있는 최적의 방법이 없습니다. 따라서, 가능한 곳에 벽 3개를 모두 세워보아야 합니다. 저는 벽을 세울 수 있는 좌표들을 담아 놓고, 하나씩 세우는 방법으로 진행하였습니다. 기본적인 브루트포스 진행방식을 이해하고 있어야 합니다.
2. 안전 영역을 구하는 방법.
=> 벽 3개를 모두 세웠으면 이제 바이러스를 퍼트려야 합니다. 바이러스는 BFS를 이용하여 퍼트렸습니다. 마지막으로, 안전 영역을 구하는 방법은 바이러스가 다 퍼진 후, 남은 영역의 개수를 세는 방식으로 진행하였습니다.
|
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
|
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
//구조체 : 좌표
struct pos {
int x, y;
};
//4방향 : 북,동,남,서
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int N, M;
int map[10][10];
vector<pos> space;
vector<pos> virus;
int copyMap[10][10];
int answer;
void spread_virus_to_copyMap() {
queue<pos> q;
//큐에 바이러스 모두 담기
for (int i = 0; i < virus.size(); i++) {
q.push(virus[i]);
}
//BFS 탐색
while (!q.empty()) {
pos cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
pos nxt = cur;
nxt.x += di[i];
nxt.y += dj[i];
if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= M) {
continue;
}
if (copyMap[nxt.x][nxt.y] == 0) {
copyMap[nxt.x][nxt.y] = 2;
q.push(nxt);
}
}
}
}
int count_safeSpace_from_copyMap() {
int safeSpaceCnt = 0;
//안전 영역(=0) 개수 세기
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copyMap[i][j] == 0) {
safeSpaceCnt++;
}
}
}
//안전 영역 반환
return safeSpaceCnt;
}
void makeWall(int spaceIdx, int wallCnt) {
//종료조건 : 벽을 3개 모두 세웠을 경우
if (wallCnt == 3) {
//시뮬레이션을 하기 위해 맵 복사
memcpy(copyMap, map, sizeof(copyMap));
//복사된 맵에 바이러스 퍼트리기(BFS)
spread_virus_to_copyMap();
//안전 영역 구하기
int safeSpaceCnt = count_safeSpace_from_copyMap();
//결과 갱신
if (safeSpaceCnt > answer) {
answer = safeSpaceCnt;
}
//종료
return;
}
//빈 공간에 벽 하나씩 세우기
for (int i = spaceIdx; i < space.size(); i++) {
/*
빈 공간 좌표 꺼내서, 벽을 세우고 탐색한 후 다시 벽 없애기
*/
int x = space[i].x;
int y = space[i].y;
map[x][y] = 1;
makeWall(i + 1, wallCnt + 1);
map[x][y] = 0;
}
}
int main() {
//초기화
answer = -1;
//입력
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
//빈 공간(=벽 세울 위치) 저장
if (map[i][j] == 0) {
space.push_back({ i,j });
}
//바이러스 위치 저장
else if (map[i][j] == 2) {
virus.push_back({ i,j });
}
}
}
//벽 세우기(브루트포스)
makeWall(0, 0);
//출력
cout << answer;
//종료
return 0;
}
|
브루트포스와 BFS에 대해 알아볼 수 있는 문제였습니다.
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 12100 - 2048(Easy) (0) | 2021.01.10 |
|---|---|
| [C++] 백준 1018 - 체스판 다시 칠하기 (0) | 2021.01.06 |
| [C++] 백준 1120 - 문자열 (0) | 2021.01.03 |
| [C++] 백준 4949 - 균형잡힌 세상 (0) | 2021.01.01 |
| [C++] 백준 10773 - 제로 (0) | 2021.01.01 |
