[ 백준 ] 17142번 - 연구소3 ( C++ )

bfs문제를 풀던 중 조금의 응용이 있는 문제다.

다른 사람의 풀이를 참고해서 풀었기 때문에 정리해보려한다.

 

<문제>

www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

<참고해서 풀은 내 풀이>

#include<bits/stdc++.h>
using namespace std;

int n,m, secureCnt=0, result=2500;
int lab[50][50] = {0,};
int visited[50][50];
int dx[4] = {0,-1,0,1}, dy[4] = {1,0,-1,0};
bool virus_visited[10] = {false,};
vector<pair<int,int>> virus;

void bfs(int size){
  queue<pair<int,int>> q;
  memset(visited, -1, sizeof(visited));
  
  for(int i=0; i<size; i++){
    if(virus_visited[i]){
      q.push({virus[i].first, virus[i].second});
      visited[virus[i].first][virus[i].second] = 0;
    }
  }
  
  int cnt=0, time=0;
  
  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) continue;
      if(lab[nx][ny]!=1 && visited[nx][ny]==-1){
        q.push({nx,ny});
        visited[nx][ny] = visited[x][y] + 1;
        if(lab[nx][ny] == 0){
          cnt++;
          time = visited[nx][ny];
        }
      }
    }
  }
  if(cnt == secureCnt) result = min(result, time);
}


void selectVirus(int index, int cnt, int size){
  if(cnt == m){
    bfs(size);
    return ;
  }
  for(int i=index; i<size; i++){
    if(!virus_visited[i]){
      virus_visited[i] = true;
      selectVirus(i+1, cnt+1, size);
      virus_visited[i] = false;
    }
  }
}


int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin>>n>>m;
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>lab[i][j];
      if(lab[i][j]==2) virus.push_back({i,j});
      else if(lab[i][j]==0) secureCnt++;
    }
  }
  
  selectVirus(0, 0, virus.size());
  if(result != 2500) cout<<result;
  else cout<<-1;
}
  

바이러스가 m개를 활성 상태로 바꾸어 bfs를 하는것이다. m개가 되는 모든 조합을 돌려보아야 하는데, 이것을 어떻게 해야할 지 감이 안잡혔다. 다른 사람의 풀이를 참고하니 재귀함수로 바이러스가 m개가 될 때 bfs를 실행했다. 

그리고 처음에 arr 배열에 0의 갯수를 secureCnt로 정하여 해당 값이 cnt와 다른 경우만 있다면 (모든 방에 감염 X) -1을 출력하였다. 조금 복잡하지만 충분히 생각할 수 있는 수준이었다. 다음에는 이 정도 수준은 쉽게 풀 수 있도록 하자.