문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
와 같아질 때 까지 증가시키며 왼쪽부터 적을 검사한다.
구현하는데 시간이 오래 걸린 이유를 생각해봤다.
- 성급하게 코딩부터 하고싶은 마음에 대각선 방향을 생각하지 못했다.
- 자꾸 vector 범위에서 0을 유효하게 하는 걸 빼먹는다.
move_cnt
를 0부터 시작했더니 직관이랑 안맞아서 헷갈렸다.