문제 이해 단계
https://www.acmicpc.net/problem/17141
17141번: 연구소 2
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이
www.acmicpc.net
NxN 크기의 맵에 M개의 바이러스를 놓으려고 한다.
바이러스는 맵에 ' 2 '라고 표시되어 있는 곳에 밖에 놓지 못한다.
바이러스는 1초당 상하좌우로 인접한
모든 빈칸(1이라고 적힌 칸을 제외)한 칸으로 퍼진다.
M개의 바이러스를 배치하여 최소한의 시간으로 모든 맵에 바이러스를 퍼뜨릴 때, 이 최소 시간은?
만약 모든 맵에 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다.
문제 접근 단계
문제 유형 추측
예전에 풀었던 연구소 1의 다음 문제 같다.
이번에도 역시 대놓고 그래프 탐색을 하라는 듯한 힌트를 마구 주었다.
바이러스가 인접한 모든 빈칸에 상하좌우로 퍼지고, 최소 시간을 구해라..
BFS를 사용하면 편하게 구할 수 있을 것 같다.
문제가 되는 점은 2라고 적힌 공간에
M개의 바이러스를 배치해야 한다는 점
각 배치에서 바이러스가 다 퍼졌을 때의 시간을 어떻게 알 수 있을까?
방법은 진짜 BFS를 실행해서 해보는 수밖에 없다.
제한 사항 체크
일단 제한 사항부터 체크해 보자.
맵(N)의 최대 크기는 50x50까지 가능하다.
그리고 바이러스(M)는 최대 10개까지 가능하다.
그러면 자연스럽게 바이러스를 둘 수 있는 공간은
맵의 최대크기에 종속받아 50x50개가 될 것임이 자명하다.
일단 맵의 크기나 바이러스의 개수가 엄청나게 작다는 것을 알 수 있다.
그래서 완전탐색을 해도 시간초과가 나지 않을 것 같다.
풀이 전략
그래서 나는 완전탐색 기법 중 하나이자,
M개의 모든 경우의 수를 살펴볼 수 있는 백트래킹을 사용하기로 하였다.
대략적인 알고리즘은 이렇다.
1. 백트래킹을 통해 바이러스를 둘 M개의 공간을 정한다.
2. 그 공간들을 큐에 넣음으로써 BFS를 시작하여
바이러스를 끝까지 퍼뜨려 시간을 계산한다.
3. 백트래킹을 통해 각기 다른 모든 경우의 수를 알 수 있으므로
그중 가장 시간이 적게 걸린 것이 답이 된다.
알고리즘 흐름만 보면 간단하다.
유의사항(체크해줘야 할 점)
해당 문제에서는 바이러스가 전체 맵에 퍼지지 못할 경우도 존재한다.
그런 경우는 제외해줘야 한다.
또한 백트래킹을 하다가
어떤 경우의 수는 바이러스가 전체 맵의 퍼지지 못할 수도 있다.
이런 경우는 BFS가 빨리 끝나 시간이 적게 나올 수 있다.
그렇기 때문에 이를 캐치하여, 이런 BFS는 제외해 주는 작업을 잘해야 한다.
문제 구현 단계
// 바이러스 둘 수 있는 공간 방문 확인용
bool visited[2500] = {false,};
vector<Point> area; // 바이러스를 둘 수 있는 공간을 담는 벡터
// M개의 바이러스를 선택하는 백트래킹
int backTracking(int x, vector<Point> virus){
// M개의 바이러스가 선택됐다면 BFS 시작
if(virus.size() >= M) return bfs(virus);
int ans = INF; // 정답을 리턴할 Ans
// 자기 자신 다음부터
for(int i = x+1; i < area.size(); i++){
int nx = area[i].x;
int ny = area[i].y;
if(visited[i]) continue;
visited[i] = true;
virus.push_back({nx,ny}); // 선택한 바이러스를 리스트에 담음
ans = min(ans,backTracking(i,virus)); // backTracking 재귀호출
visited[i] = false; // 사용한뒤 할당 해제
virus.erase(virus.begin()+virus.size()-1); // 리스트에서도 빼줌
}
return ans; // 최소값인 정답 반환
}먼저 area에서 M개의 바이러스를 고르는 백트래킹 함수이다.
매개변수로 현재 담는 바이러스 번호 인덱스와
선택된 바이러스를 담고 있는 벡터를 가진다.
선택된 바이러스가 M개가 된다면
선택된 바이러스를 인자로 넘기고 BFS를 시작한다.
백트래킹은 일반적인 백트래킹과 같다.
자기 자신 다음 인덱스부터 하나씩 읽어 backTracking을 재귀호출한다.
그 과정에서 virus 벡터에 선택한 바이러스를 넣다 뺐다
하면서 경우의 수를 계속 바꾸는 것이다.
그렇게 min()으로 정해진 ans를 반환한다.
// 좌표 구조체
struct Point{
int x;
int y;
};
int map[51][51]; // 맵
// 바이러스 확장을 하는 함수
int bfs(vector<Point> virus){
// 상하좌우
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bool myVisited[N+1][N+1]; // BFS 방문 확인
fill(&myVisited[0][0],&myVisited[N][N+1],false); // false 초기화
queue<Point> q;
for(auto it : virus) {
// 선택된 M개의 바이러스를 담고, 방문처리
q.push(it);
myVisited[it.x][it.y] = true;
}
int count = -1; // 큐에 담자마자 1 더해주기 때문에 -1부터 시작
while(!q.empty()){
int size = q.size();
count++;
// 사이즈를 체크함으로써, 원래 있던 바이러스인지, 퍼진 바이러스인지 체크
while(size--){
int x = q.front().x;
int y = q.front().y;
q.pop();
// 상하좌우 감염
for(int i = 0; i< 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵의 크기 넘어가거나, 이미 방문했거나, 벽을 만나거나 패스
if(nx < 1 || ny < 1 || nx > N || ny > N ||
myVisited[nx][ny] || map[nx][ny] == 1) continue;
myVisited[nx][ny] = true;
q.push({nx,ny});
}
}
}
// 벽을 제외하고 방문하지 않은 맵이 있다면 실패로 간주
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] == 1) continue;
if(!myVisited[i][j]) return INF;
}
}
return count; // 시간초 반환
}실질적으로 바이러스 확장을 실행하는 BFS함수이다.
매개변수로 선택받은 바이러스를 넘겨받아 큐에 넣는다.
여기서는 내부에서 방문 배열로
myVisited이라는 새로운 이차원배열을 선언해서 사용한다.
이는 어차피 계속해서 BFS를 돌려줘야 하기 때문에
전역변수보다는 지역변수로 쓰는 것이 더 낫다고 생각해서 그랬다.
BFS를 돌릴 때 큐에 크기를 먼저 체크하고 돌려줌으로써,
해당 값이 원래 있던 바이러스인지,
아니면 확장되어 큐에 들어온 바이러스인지를 체크하여 시간초를 체크할 수 있게 한다.
그 외에는 일반적인 BFS와 같다.
이후 전체 맵을 훑으면서 visited 되지 않은 좌표가 있는지 체크하고,
있다면 99999를 반환하여 min에 걸리지 않도록 한다.
여기까지가 핵심 함수에 대한 설명이고,
이제 아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 999999
int N,M;
// 좌표 구조체
struct Point{
int x;
int y;
};
// 바이러스 둘 수 있는 공간 방문 확인용
bool visited[2500] = {false,};
int map[51][51]; // 맵
vector<Point> area; // 바이러스를 둘 수 있는 공간을 담는 벡터
// 바이러스 확장을 하는 함수
int bfs(vector<Point> virus){
// 상하좌우
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bool myVisited[N+1][N+1]; // BFS 방문 확인
fill(&myVisited[0][0],&myVisited[N][N+1],false); // false 초기화
queue<Point> q;
for(auto it : virus) {
// 선택된 M개의 바이러스를 담고, 방문처리
q.push(it);
myVisited[it.x][it.y] = true;
}
int count = -1; // 큐에 담자마자 1 더해주기 때문에 -1부터 시작
while(!q.empty()){
int size = q.size();
count++;
// 사이즈를 체크함으로써, 원래 있던 바이러스인지, 퍼진 바이러스인지 체크
while(size--){
int x = q.front().x;
int y = q.front().y;
q.pop();
// 상하좌우 감염
for(int i = 0; i< 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 맵의 크기 넘어가거나, 이미 방문했거나, 벽을 만나거나 패스
if(nx < 1 || ny < 1 || nx > N || ny > N ||
myVisited[nx][ny] || map[nx][ny] == 1) continue;
myVisited[nx][ny] = true;
q.push({nx,ny});
}
}
}
// 벽을 제외하고 방문하지 않은 맵이 있다면 실패로 간주
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] == 1) continue;
if(!myVisited[i][j]) return INF;
}
}
return count; // 시간초 반환
}
// M개의 바이러스를 선택하는 백트래킹
int backTracking(int x, vector<Point> virus){
// M개의 바이러스가 선택됐다면 BFS 시작
if(virus.size() >= M) return bfs(virus);
int ans = INF; // 정답을 리턴할 Ans
// 자기 자신 다음부터
for(int i = x+1; i < area.size(); i++){
int nx = area[i].x;
int ny = area[i].y;
if(visited[i]) continue;
visited[i] = true;
virus.push_back({nx,ny}); // 선택한 바이러스를 리스트에 담음
ans = min(ans,backTracking(i,virus)); // backTracking 재귀호출
visited[i] = false; // 사용한뒤 할당 해제
virus.erase(virus.begin()+virus.size()-1); // 리스트에서도 빼줌
}
return ans; // 최소값인 정답 반환
}
int main(){
scanf("%d %d",&N,&M);
vector<Point> virus;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++){
int val;
scanf("%d",&val);
if(val == 2) area.push_back({i,j});
map[i][j] = val;
}
int ans = backTracking(-1,virus);
if(ans != INF) cout << ans;
else cout << "-1";
}
시행착오
BFS + 백트래킹이라는 건 금방 알아챘는데, 구현에서 오래 걸렸다.
2시간가량 걸린 것 같다.. 풀 때 이러면 안 되는데..
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me