문제 소개
연구소1, 2, 3번 문제는 모두 바이러스 확산을 다루고 있다.
"확산"이라는 워딩에서 바로 BFS(너비 우선 탐색)를 떠올릴 수 있다.
각 문제를 어떻게 풀어야 할지 정리해보자.
#14502 연구소 https://www.acmicpc.net/problem/14502
#17141 연구소2 https://www.acmicpc.net/problem/17141
#17142 연구소3 https://www.acmicpc.net/problem/17142
우선, 세 문제의 공통적인 조건은 다음과 같다.
- 연구소는 주어진 크기의 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다.
- 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다.
- 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.
여기서, 각 문제의 차이점은 다음과 같다.
-
빈 칸(0)들 중 3개의 칸을 골라서 벽을 세울 수 있다.
➡ 확산 후 바이러스가 퍼지지 않은 안전 영역의 크기를 구한다. -
바이러스 칸(2)들 중 M개에만 바이러스를 놓을 수 있다.
➡ 모든 빈 칸(0)에 바이러스를 퍼뜨리는 최소 시간을 구한다. -
바이러스(2) 중 M개를 활성 상태로 변경한다.
활성 상태인 바이러스만 복제가 가능하며, 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
➡ 모든 빈 칸(0)에 바이러스를 퍼뜨리는 최소 시간을 구한다.
코드의 기본 구조를 설계해보면,
int main() {
// 1. input을 받아서 초기 조건 설정
// 2. 조합을 통해 선택 가능한 경우의 수 계산
// 3. 반복문을 통해 각 경우에서 바이러스 확산 시뮬레이션 (BFS)
// 4. 각 문제에서 원하는 출력(안전 영역의 크기, 최소 시간 등) 계산
}조합 (Combination) 구하기
C++ STL인 algorithm 라이브러리의 next_permutation을 이용한다.
n개의 바이러스 중 m개를 선택할 때, 다음과 같이 조합을 구할 수 있다.
#include <algorithm>
vector<queue<int> > comb; // 조합(큐)을 담을 벡터
vector<int> virus; // n개의 바이러스의 index가 담긴 벡터
// n개의 바이러스 중 m개를 선택
void get_comb() {
vector<int> tmp;
for (int i=0; i<m; i++) tmp.push_back(1);
for (int i=0; i<n-m; i++) tmp.push_back(0);
sort(tmp.begin(), tmp.end()); // {0, 0, ... , 0, 1, 1, 1}
do {
queue<int> q;
for (int i=0; i<n; i++) {
if (tmp[i] == 1) q.push(virus[i]);
}
comb.push_back(q);
} while (next_permutation(tmp.begin(), tmp.end()));
}*참고: 햣 블로그 https://woong-jae.com/algorithm/210908-cpp-combination
BFS (Breadth-First Search)
BFS: 그래프에서 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
위 문제에서 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되므로 BFS를 이용하는 것이 적합하다.
BFS의 pseudo code는 아래와 같이 구성된다. (편의를 위해 python으로 구현)
need_visit = list() # 탐색해야하는 노드들이 담긴 큐
visited = list() # 이미 방문한 노드들이 담긴 큐
def bfs(graph, start):
need_visit.append(start)
while need_visit:
cur = need_visit.pop(0)
if cur not in visited:
visited.append(cur)
need_visit.extend(graph[cur]) # cur에 인접한 다른 노드들을 큐에 추가그래프가 상하좌우로 인접할 때에는 아래와 같이 편리하게 코드를 작성할 수 있다.
dR = [0, -1, 0, 1] # 행
dC = [1, 0, -1, 0] # 열
for way in range(4):
newR = R + dR[way]
newC = C + dC[way]이제, BFS의 기본 구조를 응용하여 각 문제를 해결할 수 있다.
#14502 연구소1
연구소의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
조건에 의해 연구소의 최대 크기는 64라는 것을 알 수 있다.
1단계. 초기 조건 설정
연구소1 문제를 풀기 위해 필요한 맵(1차원 배열로 구현)은 2가지이다.
int lab[MAX]: 해당 칸이 빈 칸인지, 벽인지, 바이러스인지 알 수 있는 맵bool visited[MAX]: 해당 칸의 방문 여부를 알 수 있는 맵
3단계. BFS
BFS (spread_virus)는 pseudo code와 유사하게 진행된다.
새로운 노드에 방문한 후, 인접한 노드가 아래
- 벽이 아닐 때 (
lab에서 확인 가능) - 아직 방문하지 않았을 때 (
visited에서 확인 가능)
두 조건을 모두 만족할 때 need_visit (아래 코드에서는 Q가 해당 역할을 수행) 큐에 추가한다. 더 이상 방문해야 할 노드가 남아있지 않을 때, 안전 영역의 크기를 계산한다.
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 64
int n{}, m{};
int lab[MAX];
bool visited[MAX]; // visited 큐의 역할
int safe_cnt{ 0 };
vector<int> virus;
vector<int> zero;
vector<vector<int> > wall;
int dr[4]{ 0, 0, -1, 1 };
int dc[4]{ -1, 1, 0, 0 };
void get_input() {
cin >> n >> m;
for (int i=0; i<n*m; i++) {
cin >> lab[i];
if (lab[i] == 0) zero.push_back(i);
if (lab[i] == 2) virus.push_back(i);
}
}
void get_comb() {
vector<int> tmp;
for (int i=0; i<3; i++) tmp.push_back(1);
for (int i=0; i<zero.size()-3; i++) tmp.push_back(0);
sort(tmp.begin(), tmp.end());
do {
vector<int> v;
for (int i=0; i<tmp.size(); i++) {
if (tmp[i] == 1) v.push_back(zero[i]);
}
wall.push_back(v);
} while (next_permutation(tmp.begin(), tmp.end()));
}
int count_safe() {
int cnt{ 0 };
for (int i=0; i<n*m; i++) {
if (lab[i] == 1) continue;
if (visited[i] == false) cnt++;
}
return cnt;
}
void spread_virus(vector<int>& w) {
queue<int> Q; // need_visit 큐의 역할
memset(visited, false, size(visited));
for (auto widx : w) lab[widx] = 1; // 연구소에 새로운 벽 표시
for (auto vidx : virus) {
Q.push(vidx); // need_visit_queue의 초기 원소
visited[vidx] = true;
}
while (!Q.empty()) {
int idx{ Q.front() };
int r = idx/m;
int c = idx%m;
Q.pop();
for (int d=0; d<4; d++) {
int nr{ r + dr[d] };
int nc{ c + dc[d] };
if (nr >= 0 and nc >= 0 and nr < n and nc < m) {
int nidx{ nr*m + nc };
if (lab[nidx] != 1 and !visited[nidx]) {
visited[nidx] = true;
Q.push(nidx);
}
}
}
}
int new_safe_cnt{ count_safe() };
if (new_safe_cnt > safe_cnt) safe_cnt = new_safe_cnt;
for (auto widx: w) lab[widx] = 0; // 연구소를 다시 원 상태로
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
get_input(); // 1. input을 받아서 초기 조건 설정
get_comb(); // 2. 조합을 통해 선택 가능한 경우의 수 계산
for (auto w : wall) spread_virus(w); // 3. 반복문을 통해 각 경우에서 바이러스 확산 시뮬레이션 (BFS)
cout << safe_cnt; // 4. 각 문제에서 원하는 출력(안전 영역의 크기, 최소 시간 등) 계산
}#17141 연구소2 & #17142 연구소3
연구소의 한 변의 길이 N이 주어진다. (5 ≤ N ≤ 50)
조건에 의해 연구소의 최대 크기는 2500라는 것을 알 수 있다.
1단계. 초기 조건 설정
연구소2,3 문제를 풀기 위해 필요한 맵(1차원 배열로 구현)은 2가지이다.
int lab[MAX]: 해당 칸이 빈 칸인지, 벽인지, 바이러스인지 알 수 있는 맵int times[MAX]: 해당 칸을 언제 방문했는 지 알 수 있는 맵
--1: 아직 방문하지 않음 (벽이거나, 비활성 바이러스일수도 있음)
-0: 초기 활성 바이러스
-n: n초에 복제된 활성 바이러스
3단계. BFS
BFS (spread_virus)는 pseudo code와 유사하게 진행된다.
새로운 노드에 방문한 후, 인접한 노드가 아래
- 벽이 아닐 때 (
lab에서 확인 가능) - 아직 방문하지 않았을 때 (
times에서 확인 가능)
두 조건을 모두 만족할 때 need_visit (아래 코드에서는 Q가 해당 역할을 수행) 큐에 추가한다. 더 이상 방문해야 할 노드가 남아있지 않을 때, 반복문이 종료된다.
4단계. 출력(최소 시간) 계산
연구소2, 3 문제에서는 연구소의 모든 빈 칸에 바이러스가 확산되었음을 확인하기 위해
zcount: 바이러스 확산 전 빈 칸의 개수infected: 새롭게 바이러스가 확산된 칸의 개수
위의 두 변수의 크기를 비교한다.
만약 infected 가 zcount 만큼 크지 않다면 바이러스가 확산되지 않은 칸이 존재함을 뜻하기 때문에 무의미하다.
연구소2 vs. 연구소3
두 문제 모두 전체 바이러스 중(2) m개의 바이러스를 선택하는 것은 동일하지만, 차이점은 소요시간 (total_time)을 계산할 때 발생한다.
- 연구소2) 선택받지 못한 바이러스는 빈 칸으로 취급
➡ 바이러스가 복제될 때마다total_time업데이트 - 연구소3) 선택받지 못한 바이러스는 비활성 바이러스로, 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
➡ 활성 바이러스가 비활성 바이러스가 있는 칸으로 갈 때는total_time업데이트하지 않음
이 부분이 처음에는 잘 이해되지 않아서 예시를 그려보았다.
3×3 크기의 연구소에서 오른쪽 아래에는 활성 바이러스, 왼쪽 위에는 비활성 바이러스가 있는 경우에 times 맵과 total_time 의 변화는 다음과 같다.
따라서, 연구소3 문제에서는 활성 바이러스가 비활성 바이러스가 있는 칸으로 갈 때는 total_time 업데이트하지 않는다.
전체 코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAX 2500
#define INTMAX 987654321
using namespace std;
int n{}, m{};
int zcount{ 0 };
int min_time{ INTMAX };
int lab[MAX];
int times[MAX];
vector<int> virus;
vector<queue<int> > comb;
int * dr = new int[4]{0, 1, 0, -1}; // left, down, right, up
int * dc = new int[4]{-1, 0, 1, 0};
void get_input() {
cin >> n >> m;
for (int i=0; i<pow(n, 2); i++) {
cin >> lab[i];
if (lab[i] == 0) zcount++;
else if (lab[i] == 2) virus.push_back(i);
}
}
void get_comb() {
vector<int> tmp;
for (int i=0; i<m; i++) tmp.push_back(1);
for (int i=0; i<virus.size()-m; i++) tmp.push_back(0);
sort(tmp.begin(), tmp.end());
do {
queue<int> q;
for (int i=0; i<tmp.size(); i++) {
if (tmp[i] == 1) q.push(virus[i]);
}
comb.push_back(q);
} while (next_permutation(tmp.begin(), tmp.end()));
}
void spread_virus(queue<int>& Q)
{
int total_time{ 0 };
int infected{ 0 };
memset(times, -1, sizeof(times));
queue<int> copyq{ Q };
while (!copyq.empty()) {
times[copyq.front()] = 0;
copyq.pop();
}
while (!Q.empty())
{
int idx = Q.front();
int r = idx/n;
int c = idx%n;
Q.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nc >= 0 && nr < n && nc < n) {
int nidx = n*nr + nc;
if (lab[nidx] != 1 && times[nidx] == -1) {
times[nidx] = times[idx] + 1;
// 연구소3 문제에서만 if문 추가
if (lab[nidx] == 0) { // 비활성 바이러스가 없던 자리일 때만
infected++;
total_time = times[nidx];
}
Q.push(nidx);
}
}
}
}
if (infected == zcount)
{
if (min_time > total_time) min_time = total_time;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
get_input();
get_comb();
for (auto q : comb) spread_virus(q);
if (min_time == INTMAX) cout << -1;
else cout << min_time;
}