[BOJ/백준][Gold5] 17141 : 연구소 2 (C++)

https://www.acmicpc.net/problem/17141

17141번: 연구소 2

 

 

[난이도] Gold5
[유형] BFS

[풀이]
바이러스가 위치할 수 있는 좌표의 최대 개수가 10개이므로 최초 바이러스의 개수 M개가
위치할 수 있는 모든 경우에 대해 BFS를 통해 시간을 구해주면 된다.
K개중에 M개를 선택하는 경우를 구하는 방법은 재귀로 해도 되지만
next_permutation을 이용해서 구할 수도 있다.
K가 5, M이 3일 때,
크기 5짜리 vector에 {0,0,1,1,1}와 같이 원소를 삽입하고,
next_permutation을 돌려주면 5개의 위치에서 세개를 고르는 모든 경우가 나온다.

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,map[52][52],total,Inf=9e8;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
bool visit[52][52];
vector<pair<int,int>> a;
vector<int> use;
int bfs(){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    int ret=0,sum=0;    
    for(int i=0;i<use.size();i++){
        if(use[i]){
            q.push({a[i].first,a[i].second});
            visit[a[i].first][a[i].second]=1;
            sum++;
        }
    }
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto qf = q.front(); q.pop();
            int y = qf.first;
            int x = qf.second;
            for(int i=0;i<4;i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(ny<0||nx<0||ny>=N||nx>=N||map[ny][nx]==1||visit[ny][nx]) continue;
                q.push({ny,nx});
                visit[ny][nx]=1;
                sum++;
            }
        }
        ret++;
    }
    return total==sum ? ret-1 : Inf;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            scanf("%d",&map[i][j]);
            if(map[i][j]==2) a.push_back({i,j});
            if(map[i][j]!=1) total++;
        }
    use.resize((int)a.size());
    for(int i=0;i<M;i++) use[i]=1;
    reverse(use.begin(),use.end());
    int ans = Inf;
    do{
        ans = min(ans,bfs());
    }while(next_permutation(use.begin(),use.end()));
    if(ans==Inf) ans=-1;
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17141.cpp