BOJ 17142, 연구소 3

Source: BOJ 17142 연구소 3

처음에 문제를 잘 못 이해해서 해결하는데 시간이 조금 걸렸다.
결국 문제의 핵심은 board판 위에 벽, 빈칸, 바이러스가 있고
바이러스중, m개를 선택하여 board판 위의 모든 빈칸에 바이러스가 퍼지는 시간을 구하는 문제였다.
필자는 비활성 바이러스도 활성이 되어야 한다고 생각해서 맞왜틀을 했다는..
결론은 완전탐색과 BFS로 문제 해결이 가능하다.

---

PS LOGIC

1. 입력으로 주어지는 보드판과 완전탐색할 시 필요한 복제본 보드판을 선언
2. 입력으로 주어지는 바이러스의 위치를 담을 vector<pair<int, int> > 선언한 후 위치 담기
3. 주어진 바이러스 중 m개만 선택할 것이므로 next_permutation을 쓰고 이때 필요한 int형 배열 mask 선언
4. do-while문을 통해 각각의 경우에 바이러스의 확산 속도 파악
5. 각각의 경우 중 바이러스의 확산시간이 가장 빠른 경우를 ans변수에 저장
6. 바이러스가 확산 시 확산 시간 출력(그렇지 않을 때 -1 출력)

---

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
//0 : 빈칸, 1: 벽, 2: 바이러스
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
int board[51][51];
int board1[51][51];
vector<pair<int, int>> v;
int mask[11];
int ans = 0x7f7f7f7f;
void func(){
  do{
    int times= 0;
    queue<pair<int, int>> Q;
    for(int i=0; i<n; i++){
      fill(board1[i], board1[i] + n, -1);}
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        if(board[i][j] == 1){
          board1[i][j] = -7;
        }
      }
    }
    for(int i=0; i<v.size(); i++){
      if(!mask[i]){
        board1[v[i].X][v[i].Y] = 0;
        Q.push({v[i].X, v[i].Y});
      }
    }
    while(!Q.empty()){
      auto cur = Q.front();
      Q.pop();
      for(int i=0; i<4; i++){
        int nx = cur.X + dx[i];
        int ny = cur.Y + dy[i];
        if(nx<0||ny<0||nx>=n||ny>=n)continue;
        if(board1[nx][ny] == -7 || board1[nx][ny] >= 0) continue;
        board1[nx][ny] = board1[cur.X][cur.Y] + 1;
        Q.push({nx, ny});
        if(board[nx][ny] != 2) times= board1[nx][ny];
      }
    }
      ans = min(ans, times);
    
  }while(next_permutation(mask, mask+v.size()));
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
      if(board[i][j] == 2){
        v.push_back({i, j});
      }
    }
  }
  fill(mask, mask+v.size(), 1);
  fill(mask, mask+m, 0);
  func();
  if(ans == 0x7f7f7f7f) cout<<-1;
  else cout<<ans;
}