연구소 3
문제 해석
모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제입니다.
가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제되며 1초 걸립니다.
M개의 바이러스를 활성상태로 변경합니다.
활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성상태가 활성상태로 변합니다.
바이러스를 어떻게 놓아도 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력합니다.
설계(5)
바이러스를 백트래킹을 이용하여 선택하고, bfs알고리즘으로 바이러스를 퍼뜨려서 최소시간을 구하면 되는 문제입니다.
여기서 주의할 점은 비활성 바이러스 또한 모두 퍼뜨려야 되는 것이 아닌 ,모든 빈칸이 바이러스로 전염되는 시간이라는 것입니다.
우선, 입력을 받을 때 빈칸의 개수를 카운트하고 바이러스 위치를 벡터에 저장합니다.
백트래킹기법으로 M개의 바이러스를 선택 (최악의 경우 10C5 = 212)합니다.
BFS알고리즘으로 바이러스를 퍼뜨리면서 빈칸에 바이러스가 전염되는 경우 카운트를 하여 원래 빈칸의 개수만큼 전염되면 바로 return하도록 합니다. O(N^2)
시간복잡도는 최악의 경우에 O(N^2x212) = 약 530,000정도로, 시간안에 충분히 구현이 가능합니다.
구현(15)
코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 50
#define INF 987654321
typedef pair<int,int> pp;
vector<pp> virus;
vector<pp> used;
int arr[MAXN][MAXN];
int total_cnt;
int ans = INF;
int N,M;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int bfs(){
// 초기화
queue<pp> q;
int visited[MAXN][MAXN] ={false,};
for (int i = 0; i < M; i++){
q.push(used[i]);
visited[used[i].first][used[i].second];
}
int cnt = 0;
int time = 0;
while (!q.empty()){
int q_size = q.size();
// 모든 빈칸에 바이러스가 퍼진 경우 바로 리턴
if (total_cnt == cnt) return time;
while (q_size--){
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k= 0 ;k< 4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx>=N || ny>=N) continue;
if (visited[nx][ny] || arr[nx][ny] == 1) continue;
if (arr[nx][ny]==0) cnt++;
visited[nx][ny] = true;
q.push({nx,ny});
}
}
time++;
}
// 모든 빈칸에 바이러스 퍼뜨릴 수 없는 경우
return -1;
}
void backtrack(int idx, int cnt){
// 최소시간이 0일 경우, 다른 경우들은 볼 필요가 없음
if (ans ==0) return;
if (cnt == M){
// 바이러스 전파
int time = bfs();
if (time!=-1 && time < ans) ans = time;
return;
}
// 바이러스 위치 선택
for (int i = idx; i < virus.size(); i++){
used.push_back(virus[i]);
backtrack(i+1,cnt+1);
used.pop_back();
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
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] == 0) total_cnt++;
else if (arr[i][j] == 2) {
virus.push_back({i,j});
}
}
}
backtrack(0,0);
if (ans == INF) cout <<"-1\n";
else cout << ans <<"\n";
return 0;
}
디버깅
모든 빈칸에 바이러스를 퍼뜨리면 바로 리턴하지 않는 실수를 하였습니다.
제출결과
12 ms
마무리
백트래킹 + bfs를 이용하는 문제였습니다.
문제를 풀어본 기억이 있어서인지 빠르게 구현하였습니다.
그러나, 지문을 제대로 읽지 않아서 실수를 하였습니다.