(C++) - 백준(BOJ) 17135번 : 캐슬 디펜스

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

구현 문제였습니다.

 

풀이방법

 1. 적이 상태를 board배열에 입력받습니다.

 2. mC3으로 궁수의 배치를 구합니다.

 3. 게임을 진행합니다.

 

   3-1. 매 궁수마다 각 적이 얼마나 떨어졌는지 거리를 구해줍니다. 그 후 가장 가깝고 왼쪽에 있는 적을 죽일 것임을 check해줍니다. *가장 왼쪽에 있는 궁수가 가까운 적을 먼저 죽이고 0으로 만들어 버린다면 틀립니다. 이유는 두 궁수로부터 가장 왼쪽에 있는 적의 거리가 같은 경우엔 동시에 그 적을 공격해야하지만 전자의 경우에 다른 적을 죽이게 되기 때문입니다. 따라서 중복되어 죽이는 것을 check를 통해 엄한 적을 죽이지 않도록 해야 합니다.

 

   3-2. check된 적들을 죽이고 죽일때마다 죽인 적 수를 1씩 더해줍니다.

 

   3-3. 모든 적들을 아래로 한 칸 전진합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, d, ans, killedEnemy;

int boardCopy[20][20],board[20][20], ck[20][20], dist[20][20], killCk[20][20];

void getDistanceFrom(int arcNum){
    memset(dist,0,sizeof(dist));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!boardCopy[i][j]) continue;
            dist[i][j] = abs(n+1 - i) + abs(arcNum - j);
        }
    }
}

void killCheck(){
    int minDist = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(dist[i][j] > d || !dist[i][j]) continue;
            minDist = min(minDist,dist[i][j]);
        }
    }
    for(int i = 1; i <= m; i++){
        for(int j = n; j >= 1; j--){
            if(minDist == dist[j][i] ){
                killCk[j][i] = 1;
                return;
            }
        }
    }
}

void goDown(){
    for(int i = 1; i <= m; i++){
        for(int j = n; j >= 1; j--){
            if(!boardCopy[j][i]) continue;
            if(j==n) boardCopy[j][i] = 0;
            else{
                boardCopy[j][i] = 0;
                boardCopy[j+1][i] = 1;
            }
        }
    }
}

bool enemyExist(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(boardCopy[i][j]) return 1;
        }
    }
    return 0;
}

void copyBoard(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            boardCopy[i][j] = board[i][j];
        }
    }
}

void killEnemy(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(killCk[i][j]) {
                killedEnemy++;
                boardCopy[i][j] = 0;
            }
        }
    }
}

void dfs(int depth, int idx){
    if(depth==3){
        killedEnemy = 0;
        copyBoard();
        while(enemyExist()){
            memset(killCk,0,sizeof(killCk));

            for(int arcNum = 1; arcNum <= m; arcNum++) {
                if(!boardCopy[n+1][arcNum]) continue;
                getDistanceFrom(arcNum);
                killCheck();
            }
            killEnemy();
            goDown();
            ans = max(ans,killedEnemy);
        }
        return;
    }

    for(int i = idx; i <= m; i++){
        if(ck[n+1][i]) continue;
        ck[n+1][i] = 1;
        boardCopy[n+1][i] = 1;
        dfs(depth+1, i+1);
        boardCopy[n+1][i] = 0;
        ck[n+1][i] = 0;
    }
}

int main(){
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> board[i][j];
        }
    }
    dfs(0,1);
    cout << ans << '\n';
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

3 3 1
0 0 1
1 0 1
1 1 0
5

3 3 1
0 0 1
0 0 1
0 0 1
3

3 3 3
0 0 1
0 0 1
0 0 1
3

3 3 3
1 0 1
1 0 1
0 1 1
6

3 3 3
1 1 1
1 1 1
1 1 1
9

3 3 2
1 1 1
1 1 1
1 1 1
9

3 3 1
1 1 1
1 1 1
1 1 1
9

3 3 10
1 1 1
1 1 1
1 0 1
8

3 3 10
0 0 1
0 1 1
1 0 0
4

3 4 10
1 0 1 0
0 1 0 1
1 0 1 0
6

3 4 10
1 0 1 1
0 1 0 1
1 0 1 1
8