[백준] 17142번 연구소 3

17142번 연구소 3

---

1. 이해하기

• 현재 비활성인 바이러스 중 M개를 선택해서 활성 상태로 바꾼다. 바이러스는 상하좌우로 인접한 빈 칸으로 동시에 복제가 된다.
• 연구소는 빈 칸, 벽, 바이러스로 이뤄져있다. 바이러스는 벽을 통과하지 못한다.
• 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
• 연구소의 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제.
• 모든 바이러스에 대해 구해보는 완전탐색 문제.

---

2. 구현하기

• 활성화 시킨 M개의 바이러스에 대해 퍼지는 시간을 구한다.

  void bfs(vector<Point> live_virus) {
      memset(virus_time,-1,sizeof(virus_time));
      queue<Point> q;
      int size = live_virus.size();
      for(int i = 0; i < size; i++) {
          Point now = live_virus[i];
          q.push({now.x,now.y});
          virus_time[now.x][now.y] = 0;
      }
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(nx < 0 or nx >= N or ny < 0 or ny >= N or map[nx][ny] == 1) continue;
              if(virus_time[nx][ny] != -1) continue;
              q.push({nx,ny});
              virus_time[nx][ny] = virus_time[x][y]+1;
          }
      }
  }

• 모든 바이러스에 대해서 M개를 고르고 그 중 바이러스가 퍼지는 최소 시간을 구한다.

  • 이때, 최소 시간의 기준은 빈 칸을 기준으로 한다. 그 이유는 문제가 모든 빈 칸에 바이러스가 있게 되는 최소 시간이기 때문이다.
  • 모든 경우에 대해서도 최소 시간이 구해지지 않는다면 MAX값을 반환한다.

  int find_finish_time() {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(map[i][j] == 0 and virus_time[i][j] == -1) return MAX;
              if(map[i][j] == 0 and virus_time[i][j] != -1) {
                  ret = max(ret,virus_time[i][j]);
              }
          }
      }
      return ret;
  }
  
  int solve(int index, int cnt, vector<Point> live_virus) {
      int size = virus.size();
      if(index == size) {
          if(cnt == M) {
              bfs(live_virus);
              return find_finish_time();
          } else return MAX;
      }
  
      int ret = MAX;
      live_virus.push_back({virus[index].x,virus[index].y});
      ret = min(ret,solve(index+1,cnt+1,live_virus));
      live_virus.pop_back();
      ret = min(ret,solve(index+1,cnt,live_virus));
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
struct Point{
    int x,y;
};
const int MAX = 987654321;
int map[50][50];
int virus_time[50][50];
vector<Point> virus;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,M;

void bfs(vector<Point> live_virus) {
    memset(virus_time,-1,sizeof(virus_time));
    queue<Point> q;
    int size = live_virus.size();
    for(int i = 0; i < size; i++) {
        Point now = live_virus[i];
        q.push({now.x,now.y});
        virus_time[now.x][now.y] = 0;
    }
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N or map[nx][ny] == 1) continue;
            if(virus_time[nx][ny] != -1) continue;
            q.push({nx,ny});
            virus_time[nx][ny] = virus_time[x][y]+1;
        }
    }
}

int find_finish_time() {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(map[i][j] == 0 and virus_time[i][j] == -1) return MAX;
            if(map[i][j] == 0 and virus_time[i][j] != -1) {
                ret = max(ret,virus_time[i][j]);
            }
        }
    }
    return ret;
}

int solve(int index, int cnt, vector<Point> live_virus) {
    int size = virus.size();
    if(index == size) {
        if(cnt == M) {
            bfs(live_virus);
            return find_finish_time();
        } else return MAX;
    }

    int ret = MAX;
    live_virus.push_back({virus[index].x,virus[index].y});
    ret = min(ret,solve(index+1,cnt+1,live_virus));
    live_virus.pop_back();
    ret = min(ret,solve(index+1,cnt,live_virus));
    return ret;
}

void input() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 2) virus.push_back({i,j});
        }
    }
}

int main() {
    input();
    vector<Point> live_virus;
    int ans = solve(0,0,live_virus);
    if(ans == MAX) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}