문제
$N\times N$정사각형 격자판 각 칸에 빈 칸, 벽, 또는 바이러스가 있다. 활성화 된 바이러스는 매 초 인접한 상하좌우 칸으로 동시에 복제된다. 바이러스 중 $M$개를 선택하여 활성화 시킬 때, 모든 빈 칸에 바이러스를 퍼뜨릴 수 있는 가장 빠른 시간을 찾는 문제이다.
접근
- 조합을 이용하여 활성화 시킬 바이러스를 고르고
- 고른 각 경우에 대해 BFS로 각 칸에 도달하는 시간을 구하였다.
1은 python이면 그냥 from itertools import combinations해서 슥삭 넘어갔을텐데, C++ stl에는 이런 게 없는 것 같았다. 그래서 어떻게 할 지 고민하다가, 조합을 고르는 index를 사전식으로 생성해주는 함수를 하나 짜버렸다.
- 먼저 index를 0,1,2,… 로 초기화 해놓고,
next_comb_index가 호출될때마다 다음 index를 만들도록 한다. - 함수가 호출될때, 먼저 index를 증가시킬 수 있는 곳을 뒤에서부터 찾아서 증가시킨다($n \choose r$일때 i번째에는 n-r+i 까지 올 수 있다.).
- 증가시킨 곳 뒷부분 인덱스는 다시 오름차순으로 놓는다.
가령 $5 \choose 3$이고 index가 $(0,2,3)$이면 그 다음은 $(0,2,4)$가 될것이고, $(0,3,4)$ 면 $(1,2,3)$이 될 것이다.
고르고 나서는 특기할 만한 점 없는 BFS다. deque로 큐를 만들고, 위에서 고른 바이러스 위치를 넣어 초기화해주었다. BFS하면서 distance[i][j] 배열 값을 모두 채우면, 그 중 빈 칸인데 가장 값이 큰 것을 가져왔다.
주의할 점
규칙에 따르면 바이러스를 복제시키는 도중 비활성화된 바이러스를 만나면, 그 바이러스가 활성화된다. 그런데 이 말은 사실 빈 칸처럼 취급해도 좋다는 의미와 같다. 빈 칸 뿐만 아니라 바이러스를 만나도 잘 복제되도록 처리하자.
Code
링크#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int A[50][50] = {0};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int index[10] = {0};
int MAX_INT = 100009;
vector<pair<int, int>> virus_pos;
bool next_comb_idx(int *arr, int n, int r) {
int pos = r - 1;
while (pos >= 0) {
if (arr[pos] != pos + n - r) {
break;
}
pos--;
}
if (pos == -1) {
return false; // end of combination
}
arr[pos]++;
for (int j = pos + 1; j < r; j++) {
arr[j] = arr[j - 1] + 1;
}
return true;
}
int bfs() {
// initalize distance array to inf.
int distance[50][50];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
distance[i][j] = MAX_INT;
}
}
// initalize BFS queue.
deque<pair<int, int>> Q;
for (int i = 0; i < M; i++) {
Q.push_back(make_pair(virus_pos[index[i]].first, virus_pos[index[i]].second));
distance[virus_pos[index[i]].first][virus_pos[index[i]].second] = 0;
}
// do BFS.
while (!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop_front();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
int nd = distance[x][y] + 1;
if (0 <= nx && nx < N && 0 <= ny && ny < N && nd < distance[nx][ny]) {
if (A[nx][ny] != 1) {
Q.push_back(make_pair(nx, ny));
distance[nx][ny] = nd;
}
}
}
}
// find maximum and return.
int ret = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] == 0) {
ret = max(ret, distance[i][j]);
}
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
// get input, save position of viruses.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
if (A[i][j] == 2) {
virus_pos.push_back(make_pair(i, j));
}
}
}
// get index of first combination
for (int i = 0; i < M; i++) {
index[i] = i;
}
// for each combination, do bfs and update ans to minimum.
int ans = MAX_INT;
do {
ans = min(ans, bfs());
} while (next_comb_idx(index, virus_pos.size(), M));
// if ans is inf, print -1.
if (ans == MAX_INT) {
ans = -1;
}
cout << ans;
return 0;
}
여담
시간 제한 0.25초로 적혀있어 제출 전에 혹시 엎어야 하고 $N=50, M=5$이고 바이러스 10개인 edge case를 직접 만들어 넣어보았는데, 생각보다 널널한 것 같으니 걱정할 필요 없는 것 같다.
한편, 각 바이러스 하나만 활성화하여 BFS한 경우를 모두 저장해두었다가 (최대 10개), 나중에 고르고 중첩만 해서 구할 수도 있다는 생각이 들었다. 선택한 2차원 배열들을 쌓았다고 생각하고 3rd axis 방향으로 maximum pooling 하는 것이다. 나중에 시간이 나면 이렇게도 구현해보아야겠다.
