어흥
[백준 17142] 연구소 3 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/17142
1. 주의할 점
- BFS 수행 도중, 0이 남아있지 않다면 BFS를 종료해도 된다
- 0이 없거나 극단적인 경우(Edge case)도 고려한다
더보기
TC #1
4 1
2 2 2 0
2 2 2 2
2 2 2 2
0 2 2 2
AC: 3
2. 구현
- 연구소에 대한 정보를 Arr[][]에 담고, 0의 개수를 Zero에 저장한다
- 바이러스의 좌표를 Virus 벡터에 담는다
- V 벡터를 통해 next_permutation을 수행하여 K개의 바이러스만 활성화 되도록 한다 → 큐에 넣는다
- BFS() 함수를 통해 바이러스를 퍼트리며 큐의 크기만큼 퍼졌다면 Zero의 개수를 확인하여 0이라면 BFS를 종료해도 된다
- Zero가 0이 아닌 경우: 연구소 전체에 퍼지지 못한 경우이므로 MAX를 Return하고 이외의 경우는 CheckAll() 함수를 통해 바이러스가 없는 지점까지 퍼지는 걸린 최대 시간을 구하여 반환한다
- 모든 경우에 바이러스가 연구소에 다 퍼지지 못했다면 -1을 출력하고, 이외의 경우는 Result를 출력한다
#define MAX 2501
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
int y,x;
};
info tmp;
vector<info> virus;
vector<int> v;
int num,k,len,result,zero;
int arr[50][50];
int check[50][50];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int checkAll(){
int cnt=0;
for(int i=0;i<num;i++)
for(int j=0;j<num;j++){
if(arr[i][j]==1 || arr[i][j]==2) continue;
if(check[i][j]==MAX) return MAX;
cnt = max(cnt, check[i][j]);
}
return cnt;
}
int bfs(){
for(int i=0;i<num;i++)
for(int j=0;j<num;j++)
check[i][j]=MAX;
queue<info> q;
for(int i=0;i<len;i++){
if(v[i]==1){
tmp.x = virus[i].x;
tmp.y = virus[i].y;
check[tmp.y][tmp.x]=0;
q.push(tmp);
}
}
int tz = zero;
while(!q.empty()){
int qs = q.size();
for(int k=0;k<qs;k++){
int cx = q.front().x;
int cy = q.front().y;
int cv = check[cy][cx];
q.pop();
for(int i=0;i<4;i++){
int nx = cx+dx[i];
int ny = cy+dy[i];
if(nx>=0 && ny>=0 && nx<num && ny<num && arr[ny][nx]!=1 && check[ny][nx]>cv+1){
check[ny][nx]=cv+1;
q.push({ny,nx});
if(arr[ny][nx]==0) tz--;
}
}
}
if(tz==0) break;
}
if(tz) return MAX;
else return checkAll();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin>>num>>k;
zero=0;
for(int i=0;i<num;i++)
for(int j=0;j<num;j++){
cin>>arr[i][j];
if(arr[i][j]==2) virus.push_back({i,j});
else if(arr[i][j]==0) zero++;
}
//초기화
result = MAX;
len = virus.size();
for(int i=0;i<len-k;i++)
v.push_back(0);
for(int i=0;i<k;i++)
v.push_back(1);
do{
int temp = bfs();
if(temp==MAX) continue;
else result = min(result,temp);
}while(next_permutation(v.begin(),v.end()));
result==MAX ? cout<<-1 : cout<<result;
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 14746] Closest Pair (C++) (0) | 2021.04.28 |
---|---|
[백준 2531] 회전 초밥 (C++) (0) | 2021.04.27 |
[백준 17143] 낚시왕 (C++) (0) | 2021.04.21 |
[백준 16920] 확장 게임 (C++) (0) | 2021.04.19 |
[백준 20058] 마법사 상어와 파이어스톰 (C++) (0) | 2021.04.15 |
Comments