14502 c++ 연구소 - 조합으로 풀기

삼성 s/w 기출문제

 

위 문제를 조합으로 내 코드보다 좀 더 깔끔한 코드 없을까 해서 구글링 해봤는데 , 딱히 없는 것 같아서 올려본다.  

 

1. 조합을 통해서 3개의 board[][]=0 ( 빈칸 ) 의 조합 구하기

2. 3개의 벽을 세운 배열 생성 하기

3. BFS 를 통해서 바이러스 영역 구하기 

를 순서대로 구현했다. 

 

cf). board[i/m][i%m] 는 일렬로 구성된 조합(next_permutation 을 사용하기 위해서는 일차원의 배열이여야 한다.)

을 사용하면서 board 배열은 2차원이기 때문에 일차원배열 -> 이차원 배열 로 바꾸는 식이다. 

이해가 가지 않으면 직접 4by6 배열을 가지고 예시를 들어보면서 이해하면 빠르다

 

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

#define X first;
#define Y second;

int n , m;
int board[10][10];
int sim[10][10];
int cnt = 0;

deque <pair<int,int>> q;

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

bool OOB(int x , int y ){
  if(x<0 || x>=n || y<0 || y>=m) return true;
  return false;
}



int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cin >> board[i][j];
      if(board[i][j]==2) q.push_back({i,j}); 
    }
  }

  vector<int> brute(n*m,1);
  fill(brute.begin(),brute.begin()+3,0);

  
  do{
    bool flg=false;
    vector<pair<int,int>> v; // 벽 후보 저장
    for(int i = 0; i < n*m; i++) {
      if(brute[i]==1) continue;
      if(board[i/m][i%m]==1 or board[i/m][i%m]==2) {
        flg=true;
        break;
      }
      v.push_back({i/4,i%4});
    }

    if(flg==true) continue; // 가능한 경우만 넘어옴
    
    // sim = board 하도록 조정
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        sim[i][j] = board[i][j];
      }
    }

    // 벽 반영하기
    for(auto e:v){
      sim[e.first][e.second] = 1;
    }

    // 바이러스 좌표 복사
    queue<pair<int,int>> virus;
    for(auto e:q) {
      virus.push(e);
    }
    // BFS
    while(!virus.empty()){
      auto e = virus.front();
      virus.pop();
      for(int i = 0; i < 4; i++){
        int nx = e.first + dx[i];
        int ny = e.second + dy[i];
        if(OOB(nx,ny)) continue;
        if(sim[nx][ny]==1 or sim[nx][ny]==2) continue;
        virus.push({nx,ny});
        sim[nx][ny] = 2;
      }
    }

    // 결과값 구하기
    int ans = 0;
    for(int i = 0 ; i<n;i++){
      for(int j = 0; j<m;j++){
        if(sim[i][j]==0) ans++;
      }
    }
    cnt = max(cnt,ans);
  }while(next_permutation(brute.begin(),brute.end()));

  cout << cnt;
  
}