백준 17135 - 캐슬 디펜스

C++

17135 번 - 캐슬 디펜스

문제

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자. 문제 출처

1. 궁수 3명을 배치한다.
2. 궁수는 거리가 D 이하인 적 하나를 공격하며, 가장 가까운 거리의 적을 공격한다.
3. 동일한 거리의 적이 존재한다면. 가장 왼쪽에 있는 적을 공격한다.
4. 적은 아래로 한 칸 이동하며, 이동 할 때 마다 궁수는 공격한다.

접근 방법

1. DFS를 이용하여 3명의 궁수를 뽑는다.
2. 적을 아래로 이동시킨다.(처음은 이동시키지 않음)
3. 각 궁수와 현재 맵에 있는 적을 하나씩 확인하여 궁수가 쏠 수 있는 거리 이내의 가장 가까운 적을 찾는다.
4. 궁수가 쏜 적의 위치를 stack에 담는다
5. 제거된 적의 위치를 stack에서 하나씩 찾으며 지도에서 제거 되었다고 표시를한다.
6. n행의 크기 만큼 적을 이동 시킨 후, 지도에서 제거 된 적의 수를 센다.
7. 그 중 가장 많이 죽인 경우의 수의 값을 저장하여 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stack>

using namespace std;

int n, m, d, answer;
int field[15][15], saved[15][15];
int visited[15];
int sel[15];

void Cal();
void chk();
void DFS(int lv, int idx);
int calDis(pair<int, int> a, int y, int x);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> field[i][j];
            saved[i][j] = field[i][j];
        }
    }
    DFS(0, 0);
    cout << answer;
}

void DFS(int lv, int idx) {
    // 3명의 궁수를 뽑는다.
    if (lv == 3) {
        Cal();
        chk();
        return;
    }
    for (int i = idx; i < m; i++) {
        if (!visited[i]) {
            sel[lv] = i;
            visited[i] = true;
            DFS(lv + 1, i + 1);
            visited[i] = false;
        }
    }
}

void Cal() {
    vector<pair<int, int>> archer;
    //궁병의 위치 설정
    for (int i = 0; i < 3; i++) {
        archer.push_back(make_pair(n, sel[i]));
    }
    int move = 0;
    int dis = 99;
    stack<pair<int, int>> kill;             // 궁수가 죽인 적을 담아 놓는 stack
    pair<int, int> lo = make_pair(-1, -1);
    // 적들이 아래로 한칸 씩 이동하기 시작한다.
    while (move != n) {
        // 왼쪽의 궁수부터 하나씩 적을 처리한다.
        for (int k = 0; k < 3; k++) {
            int ay = archer[k].first;
            int ax = archer[k].second;
            // 궁수와 가까운 적부터 먼저 확인한다.
            for (int i = n - move - 1; i >= 0; i--) {
                // 궁수가 쏠 수 없는 거리면, 종료한다.
                if (calDis(archer[k], i, ax) - move > d)
                    break;
                // 왼쪽 적부터 확인한다.
                for (int j = 0; j < m; j++) {
                    // 적과 궁수의 거리를 계산한다.
                    int diff = calDis(archer[k], i, j) - move;
                    // 적이 있는 위치고, 궁수가 쏠 수 있는 적이면
                    if (diff <= d && field[i][j] == 1) {
                        // 쏠 수 있는 적 중에서 가장 가까운 적 위치를 찾는다
                        if (diff < dis) {
                            dis = diff;
                            lo = make_pair(i, j);       // 제거한 적의 위치를 담아둔다
                        }
                        // 거리가 동일하다면, 가장 왼쪽의 적을 제거한다
                        else if (diff == dis && j < lo.second) {
                            dis = diff;
                            lo = make_pair(i, j);
                        }
                    }
                }
            }
            // -1이 아니라면 == 적을 제거하였다면 제거한 적의 위치를 저장한다
            if (lo.first != -1)
                kill.push(lo);
            dis = 99;
        }
        // 궁수가 쏜 적들을 지도에서 제거한다. 이렇게 하면, 여러 궁수가 한 적을 동시에 죽일 수 있다.
        while (!kill.empty()) {
            int y = kill.top().first;
            int x = kill.top().second;
            field[y][x] = -1;
            kill.pop();
        }
        move++;
    }
}

// 궁수와 적의 거리를 구하는 함수
int calDis(pair<int, int> a, int y, int x) {
    return abs(a.first - y) + abs(a.second - x);
}
// 제거한 적의 수를 센 뒤, 그 중 제일 큰 값을 저장한다.
void chk() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (field[i][j] == -1)
                cnt++;
            field[i][j] = saved[i][j];
        }
    }
    answer = max(answer, cnt);
}

후기 및 개선할 점

없