백준 17135번. 캐슬 디펜스(c++) / 구현

딱히 어려울 것 없는 구현 문제였다.

다만, 궁수들의 위치를 정하고 다시 배열들을 초기화해주는 작업이 필요하다는 것만 주의하면 될 것 같다.

 

// 캐슬 디펜스
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n, m, d, k;
int g[17][16] = {0, };
int game[17][16] = {0, };
int visited[16] = {0, };
pair<int, int> e[300];
pair<int, int> enemy[300]; // 적 위치
int enemyCnt = 0;
bool die[200]; // 적이 죽었는지 여부
int ans = 0, kill = 0; // 제거한 적의 수
 
// 모든 적들이 죽었는지 확인
bool isAllDie()
{
    for(int i=0; i<enemyCnt; i++){
        if(!die[i]) return false;
    }
 
    return true;
}
 
// 공수들이 공격한다.
void attack()
{ 
    vector<int> willDie; // 죽은 공수들을 모아둠
    for(int i=0; i<m; i++){
        if(visited[i]){
            vector<pair<int, int>> tmp; // (거리, 적 번호)
            for(int j=0; j<enemyCnt; j++){
                if(die[j]) continue;
                int num = abs(enemy[j].first-n)+abs(enemy[j].second-i);
                if(num>d) continue;
                tmp.push_back(make_pair(num, j));
            }
            sort(tmp.begin(), tmp.end());
            if(tmp.size()==0) continue;
 
            vector<pair<int, int>> tmp2; // (열, 적 번호)
            for(int j=0; j<tmp.size(); j++){
                if(tmp[0].first==tmp[j].first){
                    tmp2.push_back(make_pair(enemy[tmp[j].second].second, tmp[j].second));
                }
            }
 
            sort(tmp2.begin(), tmp2.end());
            int idx = tmp2[0].second;
            willDie.push_back(idx);
        }
    }
 
    for(int i=0; i<willDie.size(); i++){
        if(die[willDie[i]]) continue;
        kill++;
        die[willDie[i]] = true;
    }
}
 
// 적들이 이동한다.
void move()
{
    for(int i=0; i<enemyCnt; i++){
        if(die[i]) continue;
        int row = enemy[i].first;
        int col = enemy[i].second;
        row++;
 
        if(row==n){
            die[i] = true;
        }else{
            enemy[i].first = row;
            enemy[i].second = col;
        }
    }
}
 
void copy()
{
    kill = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            game[i][j] = g[i][j];
        }
    }
 
    for(int i=0; i<enemyCnt; i++){
        enemy[i].first = e[i].first;
        enemy[i].second = e[i].second;
    }
 
    memset(die, false, sizeof(die));
}
 
void choose(int cnt, int idx)
{
    // m열 중에 3개를 선택
    if(cnt==3){
        copy();
        while(!isAllDie()){
            attack();
            move();
        }
        ans = max(ans, kill);
        return;
    }
 
    for(int i=idx; i<m; i++){
        if(visited[i]) continue;
        visited[i] = true;
        choose(cnt+1, i);
        visited[i] = false;
    }
}
 
int main()
{
    cin>>n>>m>>d;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>g[i][j];
            if(g[i][j]==1){
                e[enemyCnt++] = make_pair(i, j);
            }
        }
    }
 
    choose(0, 0);
 
    cout<<ans<<"\n";
    return 0;
}