boj17135-풀이

boj.kr/17135 캐슬 디펜스(문제)

문제설명

---

(n, m)의 격자판 위에 적이 존재하고,
n + 1번째 줄에는 궁수가 3명이 존재한다.
궁수는 각자 한자리씩 차지하며, 겹칠 수 없다.
모든 궁수는 공통된 사거리 d를 가진다.
궁수는 거리가 닿는 적들을 공격할 수 있다.
거리 계산은 궁수와 적의 (x축 거리 + y축 거리)로 한다.
공격 우선순위는 가장 가까운 적 > 가장 왼쪽에 있는 적 순서다.
궁수가 같은 타겟을 공격할 수 있다. 게임은 궁수가 공격 후 적이 한칸 아래로 내려오도록 진행한다.
격자를 나간 적은 공격할 수 없다.

위의 조건에 따라서, 궁수를 효율적으로 배치해 최대로 죽일 수 있는 적의 수를 구하는 문제

풀이

---

탐색순서를 나타내보면 위와 같다.
각 단계를 다른 색으로 구분했는데, 이를 보면 물이 퍼지는 듯한 형태를 띈다.
퍼지는 모양을 보고 bfs탐색을 떠올렸다.
또한 이를 통해 시뮬레이션 문제라고 생각하고 접근했다.

각 턴이 지날 때, 격자의 많은 수의 적을 매번 옮겨주는 것보다는 궁수가 올라가는 방향으로 진행했다. (하나하나 옮기면 비용이 많이 들어서)

다른 궁수끼리 같은 적을 선택할 수 있기 때문에, 타겟을 지정하는 즉시 공격이 아닌, 타겟 지정 후, 턴이 끝나기 전에 공격하는 방법으로 구현했다.

궁수 위치 지정 -> m의 턴동안, 궁수 별 타겟 지정 -> 적 공격 및 사살한 적 카운트 -> 턴 증가 -> 모든 턴 종료 후 최대 사살 수 업데이트와 같은 흐름으로 구현했다.

궁수 위치 지정은 next_permutation을 통한 조합생성으로 했고,
궁수 별 타겟 지정은 bfs를 통해서 턴을 궁수의 y좌표, 조합에서 구해진 위치를 궁수의 x좌표로 해서 타겟을 지정했다.

구현

---

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;
typedef pair<int,int> pii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define y first
#define x second

int n, m, d;
vvb map(15, vb(15));
vvb isAlive;

pii operator+(pii p1, pii p2){
    return {p1.first + p2.first, p1.second + p2.second};
}

int dist(pii d1, pii d2){
    return (d1.x - d2.x) * (d1.x > d2.x ? 1 : -1) + (d1.y - d2.y) * (d1.y > d2.y ? 1 : -1);
}

bool isInArea(pii d){
    return (0 <= d.x && d.x < m) && (0 <= d.y && d.y < n);
}

// n번째 턴 start에 위치한 궁수의 타겟 좌표 반환
pii bfs(int turn, int start){
    vvb visited(n, vb(m, false));
    pii origin = {n - turn, start};
    queue<pii> q;
    q.push(origin);
    while(!q.empty()){
        pii cur = q.front();
        q.pop();
        pii ways[3] = {
            {0,-1},
            {-1, 0},
            {0, 1}
        };
        for (int i = 0; i < 3; ++i) {
            pii next = cur + ways[i];
            if(isInArea(next) && !visited[next.y][next.x] && origin.y > next.y){
                if(dist(next, origin) <= d){
                    if(isAlive[next.y][next.x])
                        return next;
                    q.push(next);
                }
                visited[next.y][next.x] = true;
            }
        }
    }
    return {-1, -1};
}

int main()
{
    cin >> n >> m >> d;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            bool b;
            cin >> b;
            map[i][j] = b;
        }
    }
    vector<int> p(m);
    for(int i = 3; i < m; ++i) {p[i] = 0;}
    p[0] = p[1] = p[2] = 1;
    int maxKilled = 0;
    do {
        int killed = 0;
        isAlive = map;
        // 궁수 자리 배치
        int archors[3];
        int idx = 0;
        for(int i = 0; i < m; ++i){
            if(p[i])
                archors[idx++] = i;
        }
        // 게임 진행(타겟 지정 -> 타겟 삭제 및 카운트 -> 턴 진행)
        pii atk[3];
        for(int t = 0; t < n; ++t){
            // 타겟 지정
            for(int a = 0; a < 3; ++a){
                atk[a] = bfs(t, archors[a]);
            }
            // 타겟 삭제, 카운트
            for(int a = 0; a < 3; ++a){
                if(atk[a].y != -1
                   && isAlive[atk[a].y][atk[a].x]){
                    isAlive[atk[a].y][atk[a].x] = false;
                    ++killed;
                }
            }
            // 턴 진행 (for문 내 ++t)
        }
        maxKilled = max(killed, maxKilled);
    } while (prev_permutation(p.begin(), p.end()));
    cout << maxKilled << endl;
    return 0;
}