캐슬 디펜스 (feat. 백준, 17135번)

캐슬 디펜스
https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int N, M, D, ans, tmp[16][16], arr[16][16], hunters[3];
bool visit[16];
int attack(){
    memcpy(tmp, arr, sizeof(tmp));
    register int attack_enemy_count = 0;
    for(register int n = N + 1; n >= 2; --n){      // 궁수의 행 위치 (N + 1 부터 2행까지)
        for(auto& hunter : hunters){
            priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;  // 거리, 열, 행 순서로 정렬
            for(register int i = 1, j; i < n; ++i)  // 1행부터 궁수의 행 위치 전까지
                for(j = 1; j <= M; ++j)
                    if(tmp[i][j] > 0){
                        auto dist = abs(i - n) + abs(j - hunter);
                        if(dist <= D)
                            q.push(make_tuple(dist, j, i));
                    }
            if(!q.empty()){
                auto x = get<2>(q.top()), y = get<1>(q.top());  // 우선순위 가장 높은 열, 행을 가져옴
                tmp[x][y] = 2;      // 궁수가 공격한 적의 위치
            }
        }
        for(register int i = 1, j; i < n; ++i)
            for(j = 1; j <= M; ++j)
                if(tmp[i][j] == 2)  // 공격당한 적 카운팅 및 초기화
                    tmp[i][j] = 0, ++attack_enemy_count;
    }
    return attack_enemy_count;
}
void arrange(register int index, register int count){
    if(count == 3){     // 궁수 3명 배치
        ans = max(ans, attack());
        return;
    }
    for(register int i = index; i < M; ++i)
        if(!visit[i]){
            visit[i] = true;
            hunters[count] = i + 1;
            arrange(i + 1, count + 1);
            visit[i] = false;
            hunters[count] = 0;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, false, sizeof(visit));
    cin >> N >> M >> D;
    for(register int n = 1, m; n <= N; ++n)
        for(m = 1; m <= M; ++m)
            cin >> arr[n][m];
    ans = 0;
    arrange(0, 0);
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. 개인적으로 가장 좋아하는 시뮬레이션 + 그래프탐색 유형의 문제입니다.
2. 궁수 3명의 배치는 dfs를 통해 조합으로 구합니다.
3. 하나의 조합에 대해서 모든 궁수와 모든 적의 위치에 대해 서로 거리 및 열의 정보를 구해서 한 궁수당 가장 우선순위가 높은 하나의 적을 공격합니다.
4. 적은 궁수의 윗 행에만 존재한다는 보장은 없습니다. (윗윗 행에 존재할 수도 있습니다.)