백준 17135번 캐슬 디펜스 문제 풀이

백준 17135번 문제 캐슬 디펜스 문제 풀이입니다.

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

N, M, D값이 크지 않으므로, 하나하나 다 따라가는 시뮬레이션 방식으로 풀이하면 됩니다.

 

test(a,b,c) 함수는 궁수의 위치가 각각 (N, a) (N, b) (N, c)일때 최대로 잡을 수 있는 적의 수를 리턴합니다.

 

choose_turn 함수는 각각의 턴마다 각각의 궁수가 공격할 적의 위치를 set에 추가합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N, M, D;
int field[16][16];
typedef struct _Pos {
    int x, y;
    bool operator<(const struct _Pos& rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }
} Pos;
inline int dist(int x1, int y1, int x2, int y2) {
    return abs(x1-x2) + abs(y1-y2);
}
inline int dist(Pos p1, Pos p2) {
    return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
void choose_target(int mmap[][16], set<Pos>& kset, int turn, int archer_pos) {
    Pos archer = { N, archer_pos };
    Pos vic_pos = { 1000, 1000 };
    int pd = dist(archer, vic_pos); //previous dist
    for (int i=0; i< N - turn; i++) {
        for (int j=0; j < M; j++) {
            if (mmap[i][j] == 0) continue;
            Pos epos = { i + turn, j };
            int d = dist(archer, epos);
            if (d <= D) {
                if (d < pd || (d == pd && epos.y < vic_pos.y)) {
                    pd = d;
                    vic_pos = epos;
                }
            }
        }
    }
    if (vic_pos.x != 1000) kset.insert({ vic_pos.x - turn, vic_pos.y });
}
int test(int a, int b, int c) {
    //archer pos = (N, a) (N, b) (N, c)
    int kill = 0; //ret val
    int mmap[16][16];
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            mmap[i][j] = field[i][j];
    
    set<Pos> kill_set;
    kill_set.clear();
    for (int t=0; t < N; t++) {
        //for each turn
        choose_target(mmap, kill_set, t, a);
        choose_target(mmap, kill_set, t, b);
        choose_target(mmap, kill_set, t, c);
        kill += (int)kill_set.size();
        for (auto& v : kill_set) {
            mmap[v.x][v.y] = 0;
        }
        kill_set.clear();
    }
    return kill;
}
int main() {
    cin >> N >> M >> D;
    for (int i=0; i < N; i++)
        for (int j=0; j < M; j++)
            cin >> field[i][j];
    
    int ans = 0;
    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++)
                ans = max(ans, test(i,j,k));
            
    cout << ans << endl;
	return 0;
}