[백준,c++] 17141번 - 연구소 2

문제

17141번: 연구소 2

 

코드

#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <map>
using namespace std;


int N, M;
int maps[51][51], cpy[51][51];
vector<pair<int,int>>virus;
vector<vector<pair<int,int>>>pick_virus;


int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int ans = 1e9;

void ncr(int index, vector<pair<int,int>>pick, int cnt){    //조합
    if(cnt==M){
        pick_virus.push_back(pick);
    }
    for(int i=index; i<virus.size(); i++){
        int x = virus[i].first;
        int y = virus[i].second;
        pick.push_back({x,y});
        ncr(i+1, pick, cnt+1);
        pick.pop_back();
    }
}


void bfs(){
    queue<pair<int,int>>q;
    int time_check[51][51] = {0, };
    
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(cpy[i][k]==2){
                q.push({i,k});
            }
        }
    }
    
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx>=0&&nx<N&&ny>=0&&ny<N){
                if(cpy[nx][ny]==0){
                    q.push({nx,ny});
                    time_check[nx][ny] = time_check[x][y] + 1;
                    cpy[nx][ny] = 2;
                }
            }
        }
    }
    
    bool flag = true;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(cpy[i][k]==0) flag = false;
        }
    }
    
    if(flag){
        int temp = -1;
        for(int i=0; i<N; i++){
            for(int k=0; k<N; k++){
                temp = max(temp, time_check[i][k]);
            }
        }
        ans = min(ans, temp);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            cin>>maps[i][k];
            if(maps[i][k]==2){
                virus.push_back({i,k});
                maps[i][k] = 0;
            }
        }
    }
    
    ncr(0,{},0);
    
    for(int i=0; i<pick_virus.size(); i++){
        memcpy(cpy, maps, sizeof(maps));
        
        for(int k=0; k<pick_virus[i].size(); k++){
            int x = pick_virus[i][k].first;
            int y = pick_virus[i][k].second;
            cpy[x][y] = 2;
        }
        
        bfs();
    }
    
    if(ans==1e9) cout<<-1;
    else cout<<ans;
    
}

 

풀이

BFS + 조합 문제였습니다. 

먼저 바이러스가 놓일 수 있는 위치를 전부 기억합니다. 그리고 기억한 바이러스 위치를 기준으로 선택할 수 있는 모든 조합을 구합니다. 그 후 바이러스를 놓아가며 일반적인 BFS탐색을 하면 됩니다. 다만 시간을 기록해야 하기 때문에 시간 테이블을 따로 두었습니다.

조합을 이용하여 BFS 탐색하는 문제는 처음 풀어본 것 같은데 연구소1, 2, 3 시리즈가 참 질 좋은 문제 같습니다.