14502 - c++

요약

바이러스가 연구실에 퍼진다 무조건 벽을 3개 세워서 최대 안전영역을 확보하는 것

---

아이디어

벽을 세울 수 있는 모든 경우의 수를 계산한다. 최대한 적은 계산을 하기 위해 조합을 사용한다.

즉 입력받으며 바이러스를 저장, 빈칸도 따로따로 저장한다.

그리고 조합을 사용해야 하므로 do while에 next_permutation을 사용한다.

 

이제 각각 벽을 세울 수 있는 곳에 벽을 세우고 난 후 바이러스를 전파 시킨 다음 안전영역을 계산한다.

---

CODE

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m, result = 0;
int board1[9][9], board2[9][9];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

//초기 바이러스, 빈칸의 위치를 저장
vector<pair<int, int>>zero,virus;

bool OOB(int nx, int ny){
  return nx < 0 || nx >= n || ny < 0 || ny >= m;
}

void bfs(){
	//새로운 바이러스 큐를 만듬
  queue<pair<int, int>> V;
  
  //바이러스 큐에 초기 바이러스 저장
  for(auto i : virus)V.push(i);
  
  //bfs
  while(!V.empty()){
    auto cur = V.front();V.pop(); 
    for(int dir = 0; dir < 4; ++dir){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(OOB(nx, ny) || board2[nx][ny] != 0)continue;
      V.push({nx, ny});
      board2[nx][ny] = 2;
    }
  }
}

int main()
{
  init();
  cin >> n >> m;
  for(int i =0; i < n; ++i){
    for(int j =0; j < m; ++j){
      cin >> board1[i][j];
      if(board1[i][j] == 2)virus.push_back({i, j});
      else if(board1[i][j] == 0)zero.push_back({i, j});
    }
  }

	// 조합을 위한 배열 초기화
  vector<bool> per(zero.size(), 1);
  per[0] = per[1] = per[2] = 0;

  do{
    //연구실 복사
    for(int i =0; i < n; ++i)
      for(int j =0; j < m; ++j)
        board2[i][j] = board1[i][j];

    //벽 3개 세우기(조합 사용)
    for(int i = 0; i < zero.size(); ++i)
      if(per[i] == 0)
        board2[zero[i].X][zero[i].Y] = 1;

    bfs();
    
    //안전영역 계산
    int ans = 0;
    for(int i =0; i < n; ++i)
      for(int j =0; j < m; ++j)
        ans += (board2[i][j] == 0);
    result = max(ans, result);
  }while(next_permutation(per.begin(), per.end()));
  
  cout << result;
  return 0;
}

---

연산 횟수

최대 조합의 수 : 37820

각 경우의 수마다의 배열 복사 : 64

마지막 안정영역 계산 : 64

총  : 154,910,720

 

2초 안에 모든 계산이 가능하여 통과 가능 하지 않았나 싶다.

---

문제를 풀며

바이러스를 전파 시킬때 bfs에서 원본 바이러스 큐를 사용하여 bfs()를 돌리는 참사를 저질렀다.

이렇게 되면 다음 벽을 3개 세우고  바이러스를 전파시킬 때 원본 바이러스 큐에 남아 있는 게 없으니 bfs를 돌지 못하게 된다.

그래서 따로 함수안에 새로운 바이러스 큐를 만들어서 사용하는 방법으로 바꿨다.