문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다. baekjoon

코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n, m, d, total_enemy = 0, cur_total_enemy = 0;
int result = 0;

void kill(int warrier_col, vector<vector<int>> &v, vector<pair<int, int>> &enemy) {
  int move_cnt = 1;
  if (v[n - 1][warrier_col] == 1) {
    enemy.push_back(pair<int, int>(n - 1, warrier_col));
    return;
  }
  move_cnt++;

  while (move_cnt <= d) {
    // 좌
    if (warrier_col - move_cnt + 1 >= 0 && v[n - 1][warrier_col - move_cnt + 1] == 1) {
      enemy.push_back(pair<int, int>(n - 1, warrier_col - move_cnt + 1));
      return;
    }

    int diagonal = move_cnt - 2, diagonal_row = n - 2, diagonal_col = warrier_col - diagonal;
    while (diagonal > 0) {
      bool is_valid = diagonal_row >= 0 && diagonal_row < n && diagonal_col >= 0 && diagonal_col < m;
      if (is_valid && v[diagonal_row][diagonal_col] == 1) {
        enemy.push_back(pair<int, int>(diagonal_row, diagonal_col));
        return;
      }
      diagonal--; diagonal_row--; diagonal_col++;
    }

    // 상
    if (n - move_cnt >= 0 && v[n - move_cnt][warrier_col] == 1) {
      enemy.push_back(pair<int,int>(n - move_cnt, warrier_col));
      return;
    }
    
    diagonal = move_cnt - 2, diagonal_row = n - 1 - diagonal, diagonal_col = warrier_col + 1;
    while (diagonal > 0) {
      bool is_valid = diagonal_row >= 0 && diagonal_row < n && diagonal_col >= 0 && diagonal_col < m;
      if (is_valid && v[diagonal_row][diagonal_col] == 1) {
        enemy.push_back(pair<int, int>(diagonal_row, diagonal_col));
        return;
      }
      diagonal--; diagonal_row++; diagonal_col++;
    }

    // 우
    if (warrier_col + move_cnt - 1 < m && v[n - 1][warrier_col + move_cnt - 1] == 1) {
      enemy.push_back(pair<int, int>(n - 1, warrier_col + move_cnt - 1));
      return;
    }
    move_cnt++;
  }
}

void move_down(vector<vector<int>> &v) {
  int tmp, before;
  for (int j = 0; j < m; j++) {
    before = v[0][j];
    for (int i = 1; i < n; i++) {
      tmp = v[i][j];
      v[i][j] = before;
      before = tmp;
    }
  }
  for (int i = 0; i < m; i++) v[0][i] = 0;

  cur_total_enemy = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (v[i][j] == 1) cur_total_enemy++;
    }
  }
}

int main() { 
  cin >> n >> m >> d;

  vector<vector<int>> v(n, vector<int>(m));
  vector<vector<int>> v_origin(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> v[i][j];
      v_origin[i][j] = v[i][j];
      if (v[i][j] == 1) total_enemy++;
    }
  }

  int result = 0;
  vector<pair<int, int>> enemy;
  for (int i = 0; i < m - 2; i++) {
    for (int j = i + 1; j < m - 1; j++) {
      for (int k = j + 1; k < m; k++) {
        int kill_num = 0;
        cur_total_enemy = total_enemy;
        v = v_origin;

        while (cur_total_enemy > 0) {
          enemy.clear();
          kill(i, v, enemy);
          kill(j, v, enemy);
          kill(k, v, enemy);

          set<pair<int, int>> st;
          for (int l = 0; l < enemy.size(); l++) {
            pair<int, int> p = enemy[l];
            if (st.count(p) == 0) {
              v[p.first][p.second] = 0;
              st.insert(p);
              kill_num++;
            }
          }
          move_down(v);
        }
        result = max(result, kill_num);
      }
    }
  }

  cout << result << endl;
}

풀이

궁수는 3명밖에 안되니까 3중 for loop면 금방 조합할 수 있다. 궁수 위치가 정해지면 적이 0명이 될 때 까지 각자 궁수가 죽이고, 한칸씩 내리기를 반복한다.

move_cnt를 d와 같아질 때 까지 증가시키며 왼쪽부터 적을 검사한다.

구현하는데 시간이 오래 걸린 이유를 생각해봤다.

1. 성급하게 코딩부터 하고싶은 마음에 대각선 방향을 생각하지 못했다.
2. 자꾸 vector 범위에서 0을 유효하게 하는 걸 빼먹는다.
3. move_cnt를 0부터 시작했더니 직관이랑 안맞아서 헷갈렸다.