백준 17135 캐슬 디펜스

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 적들이 주어진 맵에 존재하고 성벽에 궁수 3명이 있을때 궁수들의 위치를 배치하여 가장 적을 많이 처치 할 수 있는 수를 구하는 문제입니다. 모든 가능한 궁수들의 배치에 대하여 각각 시뮬레이션을 해보면 됩니다. 

 

주어진 조건에 따라 현재 제거할 수 있는 가장 가까운 적(거리가 가장가까운)들을 차례대로 제거하고 적들을 한칸씩 아래로 내리면서 더이상 적이 없을때까지 진행해주시면 됩니다. 저는 벡터에 적들의 좌표를 유지시키면서 풀었습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int N,M,D;
int ans;

int sol(int a, int b, int c, vector<pair<int, int> > v, int enemy) {
    if(v.size() == 0) //적이 없음
        return enemy;

    vector<pair<int, int> > vc = v;
    int d[3];
    int arc[3];
    arc[0] = a;
    arc[1] = b;
    arc[2] = c;
    d[0] = 100;
    d[1] = 100;
    d[2] = 100;
    int pos[3];
    memset(pos, -1, sizeof(pos));

    for(int i = 0; i < vc.size(); i++) {
        for(int j = 0; j < 3; j++) {
            int dd = abs(vc[i].first-N)+abs(vc[i].second-arc[j]);
            if(d[j] >= dd) {
                if(d[j] == dd) { // 거리가 같은경우 왼쪽 좌표를 비교하여 판단
                    if(vc[pos[j]].second > vc[i].second)
                        pos[j] = i;
                }
                else {
                    pos[j] = i;
                }
                d[j] = dd;
            }
        }
    }

    for(int i = 0; i < 3; i++) { // 궁수에게 제거당한 적 표시
        if(vc[pos[i]].first != -1 && d[i] <= D) {
            vc[pos[i]].first = -1;
            vc[pos[i]].second = -1;
            enemy++;
        }
    }
    vector<pair<int, int> > p;
    for(auto n : vc) { // 남은 적들 아래로 한칸씩 이동
        if(n.first != -1 && n.first+1 < N) {
            p.push_back({n.first+1, n.second});
        }
    }
    return sol(a, b, c, p, enemy);
}

int select(vector<pair<int, int> > v) { // 가능한 궁수의 조합
    for(int i = 0; i < M; i++)
        for(int j = i+1; j < M; j++)
            for(int k = j+1; k < M; k++) {
                ans = max(ans, sol(i,j,k, v, 0));
            }
    return ans;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M >> D;
    int maze[16][16];
    vector<pair<int, int> > v;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) {
            cin >> maze[i][j];
            if(maze[i][j] == 1)v.push_back({i,j}); //적 좌표 저장
        }
    cout<<select(v);
    return 0;
}