[BOJ/C++] 14502번 연구소
문제
문제 해석
연구소는 빈 칸과 벽으로 이루어져 있다. 이곳에 2개 이상의 바이러스가 존재하는데, 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나간다. 벽을 딱 3개 세워서 바이러스가 퍼지지 않게 막고, 바이러스가 퍼지지 않은 안전 영역의 최댓값을 구하는 문제이다.
아이디어
빈 칸에는 전부 벽을 세울 수 있다. 빈 칸 N개 중 3개를 골라 벽을 세우고, 바이러스를 퍼뜨린 뒤, 안전 영역을 구하고 저장한다. NC3 개의 안전 영역 중에서 최댓값을 출력한다.
문제의 흐름 그대로 구현해야 하는 문제라고 생각했다.
시간복잡도
next_permutation을 이용해 빈 칸 N개 중 3개를 고른다.O(NC3) = O(N^3)BFS알고리즘으로 바이러스를 퍼뜨린다.O(N^2)안전 영역을 구하고 저장한다.
O(1)
구현 전 대략적인 시간 복잡도를 O(N^5)로 생각했기 때문에 무리 없이 통과할 것이라고 생각했다.
구현 방향
변수 선언
✅ 다른 블로그의 풀이를 보니 연구소 원본의 배열을 기록해두고 벽을 세울 때마다 연구소 배열을 복사해서 사용하는 것 같았다. 하지만 나는 벽을 1로 세우고 계산이 끝나면 다시 0으로 설정하는 방식을 택했다. 어느 쪽이든 구현에 자신 있는 방향으로, 시간 제한을 넘지 않는 선에서 선택하면 된다.
계산한 안전 영역을 safety에 저장하고, 정렬한 후 최댓값을 구해야 하므로 #include <algorithm>을 선언한다.
NC3번 벽을 세울 때마다 BFS 알고리즘을 이용해 바이러스를 퍼뜨린다. memset을 이용해 visited를 초기화 하므로 #include <string.h>을 선언한다.
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>;
using namespace std;
int N, M; // height, width
int board[8][8];
int visited[8][8];
int virus_safety = 0;
int wall_count = 0;
typedef struct location {
int row, col;
};
vector<location> spaces;
vector<location> viruses;
queue<location> q;
vector<int> safety;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int main()
// input
✅ 빈 칸은 벽을 세울 수 있는 공간이므로 spaces에 저장한다. 안전 영역을 셀 때 벽은 제외하므로 초기 벽의 개수도 저장한다.
// choose wall position 3
✅ next_permutation을 이용해 조합을 구현한다. 빈 칸인 spaces 중에서 3개를 골라 벽을 세우므로, 임의의 temp 벡터에 3개의 1을 넣고, 나머지는 0을 넣는다. 오름차순으로 temp 벡터를 정렬한다. 이후 do {...} while(next_permutation(temp.begin(), temp.end()));에서 조합을 구현한다.
// make 3 walls
temp 배열에서 1인 값이 NC3 조합으로 선택된 벽들이다. board에 벽을 세운다. board 위치에 바로 벽을 세울 수 있도록, 빈 칸을 따로 spaces에 저장했다.
// viruses BFS 알고리즘으로 virus를 퍼뜨린다.
// count safety_area virus가 방문하지 않은 곳을 세서 안전 영역을 계산한다.
// initialize 다음 while을 위해 변수들을 초기화 한다. 세웠던 벽들도 다시 빈 칸으로 만든다.
// find max safety area size
do {} while 문에서 모든 NC3 케이스에 대해 안전 영역 계산을 끝낸 후, 오름차순으로 정렬해 최댓값을 출력한다.
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
int main() {
// input
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
if (board[i][j] == 2) {
viruses.push_back({ i, j });
}
else if (board[i][j] == 0) {
spaces.push_back({ i, j });
}
else if (board[i][j] == 1) wall_count++;
}
}
// choose wall position 3
vector<int> temp;
for (int i = 0; i < 3; i++) { temp.push_back(1); }
for (int i = 0; i < spaces.size() - 3; i++) { temp.push_back(0); }
sort(temp.begin(), temp.end());
do {
// make 3 walls
for (int i = 0; i < temp.size(); i++) {
if (temp[i] == 1) { board[spaces[i].row][spaces[i].col] = 1; }
}
// viruses;
for (int i = 0; i < viruses.size(); i++) {
bfs(viruses[i].row, viruses[i].col);
}
// count safety_area
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visited[i][j] == 1) virus_safety++;
}
}
safety.push_back(N * M - (wall_count + 3) - virus_safety);
// initialize
memset(visited, 0, sizeof(visited));
virus_safety = 0;
for (int i = 0; i < temp.size(); i++) {
if (temp[i] == 1) { board[spaces[i].row][spaces[i].col] = 0; }
}
} while (next_permutation(temp.begin(), temp.end()));
// find max safety area size
sort(safety.begin(), safety.end());
cout << safety[safety.size() - 1] << "\n";
}
void bfs(int row, int col)
✅ 모듈화의 관점에서, push와 visited 체크를 함수 안에 작성했다. 큰 구조는 일반적인 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
void bfs(int row, int col) {
// initialize
q.push({ row, col });
visited[row][col] = 1;
while (!q.empty()) {
int row = q.front().row;
int col = q.front().col;
q.pop();
for (int d = 0; d < 4; d++) {
int next_row = row + dx[d];
int next_col = col + dy[d];
if (next_row >= 0 && next_row < N
&& next_col >= 0 && next_col < M
&& board[next_row][next_col] != 1
&& visited[next_row][next_col] != 1) {
q.push({ next_row, next_col });
visited[next_row][next_col] = 1;
}
}
}
}
막힌 부분
✅ 빈 칸 N개 중 3개를 고르는 코드 구현이 까다로웠다. NC3 조합을 구현해야 했는데, 버벅 거려서 next_permutation 예제를 보고 조합을 구현했다. 가장 도움이 된 블로그를 첨부한다. 이해가 됐다면 체화하기 위해 백준의 N과 M 시리즈를 풀어보자.