[백준 17135] 캐슬 디펜스 (C++)

17135번: 캐슬 디펜스

 

오랜만에 풀어본 백준!

 

백트래킹을 사용한 완전탐색 문제였다.

 

주의해야할 궁수의 공격 특징은 다음과 같다.

1. 모든 궁수는 동시에 공격하며 같은 대상을 공격할 수 있다. (같은 적이 여러 궁수에게 공격당할 수 있다.)
2. 적과의 거리가 D이하이면 공격한다.
3. 가장 가까운 적을 공격한다. (가장 가까운 적이 어렷일 시 가장 왼쪽의 적을 공격한다.)

 

1번과 3번 특징 때문에 궁수의 위치에 따라서 잡을 수 있는 적의 수가 달라질 수 있다는 것을 눈치채야 한다.

궁수가 적절히 배치되어 적을 중복해서 공격하는 경우를 최소화 하며, 가장 많이 잡을 수 있는 위치에 배치되어야 한다.

이 조건에 부합하는 위치를 찾으려면 매우 어려울 것이다.

그래서 N, M, D와 궁수의 수(3) 의 수가 작기 때문에 완전탐색을 사용해야 수월하게 풀 수 있다.

 

 

1. 궁수의 위치 찾기

격자판의 열의 수가 M이면 궁수가 배치될 수 있는 경우의 수는 M개중 3개를 뽑는 경우의 수이다. (MC3)

-> 백트래킹으로 찾아준다.

 

 

2. 적 공격

현재 궁수의 위치는 N이 될 것이고 매 턴마다 한 행씩 위로 올려준다.

 

2.1 현재 궁수에 대해서 공격가능한 적의 위치를 벡터에 저장한다.

2.2 적의 위치를 정렬한다. 이때 '거리가 가까운 순 + 거리가 같은 경우 가장 왼쪽의 적'을 기준으로 정렬한다.

2.3 현재 궁수가 공격할 적은 정렬된 벡터의 첫 번째 원소일 것이다. 따라서 해당 적을 또 다른 벡터에 저장한다.

2.4 모든 궁수에 대해서 2.1 ~ 2.3을 반복한다.

2.5 모든 궁수가 공격할 적이 정해졌으면 적을 공격하고 잡은 적의 수를 +1 한다. (중복을 피해야 함)

2.6 궁수가 위치한 행이 0행이 되면 공격한 적의 수를 반환한다.

 

3. 최댓값을 갱신한다.

3.1 다른 궁수배치에 대해 2. 과정을 수행하기 위해 격자판을 초기화 해준다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;

int OriginMap[16][16];
int Map[16][16];
int N, M, D;
int answer;

void input(){
    cin >> N >> M >> D;
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            cin >> Map[r][c];
            OriginMap[r][c] = Map[r][c];
        }
    }
}

inline int dist(int r1, int c1, int r2, int c2){
    return abs(r1-r2) + abs(c1-c2);
}

struct T{
    int r, c, d;
};

bool cmp(T &a, T &b){
    if(a.d == b.d) return a.c < b.c;
    else return a.d < b.d;
}

void copyMap(){
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            Map[r][c] = OriginMap[r][c];
        }
    }
}

int attack(vector<int> &archerCols){
    int ret = 0;
    
    int archerRow = N;
    while(archerRow >= 1){
        vector<pii> ex;
        for(auto &archerCol: archerCols){
            vector<T> target;
            for(int r = 0; r < archerRow; r++){
                for(int c = 0; c < M; c++){
                    if(!Map[r][c]) continue;
                    if(dist(r, c, archerRow, archerCol) > D) continue;
                    target.push_back({r, c, dist(r, c, archerRow, archerCol)});
                }
            }
            if(target.empty()) continue;
            sort(target.begin(), target.end(), cmp);
            ex.push_back({target[0].r, target[0].c});
        }
        
        for(auto &e: ex){
            if(Map[e.first][e.second] == 1){
                Map[e.first][e.second] = 0;
                ret++;
            }
        }
        
        archerRow--;
    }
    
    return ret;
}

void archerCombination(int n, int i, vector<int> &archerCol){
    if(n == 3){
        copyMap();
        answer = max(answer, attack(archerCol));
        return;
    }
    
    for(int k = i; k < M; k++){
        archerCol.push_back(k);
        archerCombination(n+1, k+1, archerCol);
        archerCol.pop_back();
    }
}


void solve(){
    vector<int> archerCol;
    archerCombination(0, 0, archerCol);
    cout << answer;
}

int main(){
    input();
    solve();
    
    return 0;
}