2023. 8. 3. 13:20ㆍ카테고리 없음
문제
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.
입력
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 비활성 바이러스의 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
출력
연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
풀이법
해당 문제의 풀이법은 먼저 백트래킹을 통해 활성화시킬 바이러스를 정한다. M개 만큼을 정했으면 그 때 bfs를 통해 바이러스를 전파시킨다.
이 때, 시간을 유의해서 풀어야한다.
나는 visited 배열을 둔 후에 배열의 값으로 시간을 갖게 했다. 즉, 처음으로 활성화된 바이러스는 0, 그 바이러스 근처에 있는 바이러스는 1, 이런식으로 값을 둔 후에 실제 빈 칸 값이 갖는 visited 배열의 값만 알면 되니까 그 때 max 값을 가져왔다.
에러 고친 것
이번에도 역시 몇번 틀렸다. 처음 컴파일 에러는 헤더 파일을 써주지 않아서 났었다.
1. 시간 초과는 처음에는 매번 bfs를 돌 때마다 모두 탐색이 끝났는지 전체 배열을 둬서 확인했는데 그러니까 for 루프가 5개 정도 중첩되면서 시간 초과가 났다. 그래서, 빈칸의 개수를 num_zero로 처음에 초기화해준 후 매번 큐에 넣을 때 num_zero와 비교해서 같은 값이 되면 전체를 확인했다고 생각해서 루프를 빠져나왔다.
2. dfs 를 돌 때 dfs(cnt+1, start+1) 이라고 줘서 시간초과가 났다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <cstring>
using namespace std;
int N, M;
int num_zero;
int total = INT_MAX;
int arr[51][51];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1,-1, 0, 0 };
vector<pair<int, int>> candidate;
vector<pair<int, int>> active_virus;
int bfs(void) {
int visited[51][51];
memset(visited, -1, sizeof(visited));
queue<pair<int, int>> q;
for (int i = 0;i < active_virus.size();i++) {
q.push({ active_virus[i].first, active_virus[i].second });
visited[active_virus[i].first][active_virus[i].second] = 0;
}
int end = 0;
while (!q.empty()) {
int bx = q.front().second;
int by = q.front().first;
q.pop();
for (int i = 0;i < 4;i++) {
int nx = bx + dx[i];
int ny = by + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= N || arr[ny][nx] == 1 || visited[ny][nx]!=-1) {
continue;
}
visited[ny][nx] = visited[by][bx] + 1;
if (arr[ny][nx] == 0) {
end++;
}
q.push({ ny, nx });
}
if (end == num_zero) {
break;
}
}
int ans = -1;
for (int i = 0;i < N;i++) {
for (int j = 0;j < N;j++) {
if (arr[i][j] == 0 && visited[i][j] == -1) {
return -1;
}
if (arr[i][j] == 0) {
ans = max(ans, visited[i][j]);
}
}
}
if (ans == -1) ans = 0;
return ans;
}
void choose(int cnt, int start) {
if (cnt == M) {
int ret = bfs();
if (ret != -1) {
total = min(ret, total);
return;
}
}
for (int i = start;i < candidate.size();i++) {
active_virus.push_back({candidate[i].first, candidate[i].second});
choose(cnt + 1, i + 1);
active_virus.pop_back();
}
}
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 0;i < N;i++) {
for (int j = 0;j < N;j++) {
cin >> arr[i][j];
if (arr[i][j] == 2) {
candidate.push_back({ i, j });
}
else if (arr[i][j] == 0) {
num_zero++;
}
}
}
choose(0, 0);
if (total == INT_MAX) {
cout << "-1" << endl;
}
else {
cout << total << endl;
}
return 0;
}