(백준 c++)17135 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

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

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

 

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main(void){
    int N, M, D, ans = 0;

    cin >> N >> M >> D;

    vector<vector<int>> board(N + 2, vector<int>(M + 2, 0));
    vector<vector<int>> copyBoard(N + 2, vector<int>(M + 2, 0));
    vector<pair<int, int>> archers(3, pair<int, int>(make_pair(N + 1, 0)));

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> board[i][j];
        }
    }
    

    //궁수 배치
    for(int i = 1; i <= M; i++){
        archers[0].second = i;

        for(int j = i + 1; j <= M; j++){
            archers[1].second = j;
            
            for(int k = j + 1; k <= M; k++){
                int current = 0;
                vector<pair<int, int>> enemies(3);
                //원래 적의 위치를 copy_board에 복사
                copyBoard = board;
                archers[2].second = k;

                for(int turn = 0; turn <= N; turn++){
                    for(int p = 0; p < 3; p++){
                        //맵에 존재하는 적의 위치 중 D 이하인 적의 거리 구하기.
                        int distance = INT_MAX;
                        int targetX = INT_MAX, targetY = INT_MAX;

                        for(int x = N; x > 0; x--){
                            for(int y = 1; y <= M; y++){
                                if(abs(archers[p].first - x) + abs(archers[p].second - y) <= D){
                                    if(copyBoard[x][y]){
                                        if(distance >= abs(archers[p].first - x) + abs(archers[p].second - y)){
                                            if(distance == abs(archers[p].first - x) + abs(archers[p].second - y)){
                                                if(y < targetY){
                                                    targetX = x;
                                                    targetY = y;
                                                }
                                            }
                                            else{
                                                distance = abs(archers[p].first - x) + abs(archers[p].second - y);
                                                targetX = x;
                                                targetY = y;
                                            }
                                            
                                        }
                                    }
                                }
                            }
                        }

                        //만약 적의 위치가 INT_MAX인 경우 없다는 뜻이므로 0, 0으로 저장.
                        //아닌 경우 적의 위치를 저장.
                        if(targetX == INT_MAX || targetY == INT_MAX){
                            enemies[p].first = 0;
                            enemies[p].second = 0;    
                        }
                        else{
                            enemies[p].first = targetX;
                            enemies[p].second = targetY;
                        }
                    }

                    //적 제거
                    for(int p = 0; p < 3; p++){
                        if(copyBoard[enemies[p].first][enemies[p].second]){
                            copyBoard[enemies[p].first][enemies[p].second] = 0;
                            current++;
                        }
                    }
                    
                    //적 이동
                    for(int x = N; x > 0; x--){
                        copyBoard[x] = copyBoard[x - 1];
                    }
                }
                ans = ans < current ? current : ans;
            }
        }
    }

    cout << ans;

    return 0;
}