[C언어/C++] 17135 캐슬 디펜스

문제가 귀찮지만, 하나씩 뜯어보면 어렵지 않다. 

아무래도 '구현' 문제니까, 정답을 보기 전에 직접 구현해보기를 추천한다~~

 

---

구현사항이 많다.

• 궁수 3마리 배치
• bfs로 가까운 적 찾기
• 적 삭제
• 적 이동
• 게임 종료

위의 사항들을 주석을 달아서 분리하거나, 함수화하여 문제를 해결하면 그래도 가독성 있게, 디버깅 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n,m,d, ans;
int arr[16][16], brr[16][16];
int dx[4] = {0, -1, 1,0}, dy[4] = {-1, 0, 0, 1};
queue< pair< int, int > > Q;

void bfs(int bow) {
  int vis[16][16] = {};
  auto bowP = make_pair(n, bow);
  vis[n][bow] = 1;

  Q.push(bowP);

  bool flag = 0;
  
  while(!Q.empty()) {
    auto cur = Q.front(); Q.pop();
    for(int i = 0; i < 4; i++) {
      int nx = cur.first + dx[i];
      int ny = cur.second + dy[i];
      if(nx < 0 || nx >= n + 1 || ny < 0 || ny >= m + 1) continue;
      
      if(vis[nx][ny]) continue;

      if(brr[nx][ny]) {
        vis[nx][ny] = vis[cur.first][cur.second] + 1;
        brr[nx][ny] = 2;
        flag = 1;
        break;
      }
      vis[nx][ny] = vis[cur.first][cur.second] + 1;
      if(vis[cur.first][cur.second] + 1 > d) continue;
      Q.push(make_pair(nx, ny));
    }
    if(flag) break;
  }

  while(!Q.empty()) Q.pop();
}

void fight(int fir, int sec, int thi) {

  int tmp = 0;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      brr[i][j] = arr[i][j];
    }
  }

  bool repeat = 1;

  while(repeat) {
    repeat = 0;
    
    // 궁수 하나씩 제일 가까운 적 찾기
    bfs(fir);
    bfs(sec);
    bfs(thi);  

    // 그 적 삭제하기
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(brr[i][j] == 2) {
          brr[i][j] = 0;
          tmp++;
        }
      }
    }

    // 한 칸씩 내리기
    for(int i = n - 2; i >= 0; i--) {
      for(int j = 0; j < m; j++) {
        brr[i + 1][j] = brr[i][j];
        brr[i][j] = 0;
      }
    }

    // 비었나 체크
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(brr[i][j]) repeat = 1;
      }
    }
  }

  ans = max(ans, tmp);
}


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

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cin>>arr[i][j];
    }
  }

  for(int i = 0; i < m; i++) {
    for(int j = i + 1; j < m; j++) {
      for(int k = j + 1; k < m; k++) {
        fight(i, j, k);
      }
    }
  }

  cout<<ans;
}