[baekjoon] 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은 적이 있는 칸이다.

출력

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

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

예제 입력

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

예제 출력

3

풀이

궁수 3명을 성에 배치 시켜서 몰려오는 적을 물리친다.

가장 많이 물리 칠 수 있는 적의 수를 구하는 문제다.

쉽게 그린 문제 설명

배치할 수 있는 궁수의 최대 수가 3명이기때문에 배치할 수 있는 모든 경우에 대해서 시뮬레이션을 돌린다.

주의해야할 점은 궁수는 자신이 공격할 수 있는 범위에서 가장 가까운 적을 공격한다. 가장 가까운 적이 여러명이면 가장 왼쪽의 적을 공격한다.

그리고 궁수는 한 번에 공격하기 때문에 동일한 대상을 공격할 수도 있다.

 

위의 두가지를 고려하기 위해서 궁수가 공격할 수 있는 적을 탐색할 때 순서를 왼쪽, 위, 오른쪽 순서로 한다.

예를 들어 궁수의 사거리가 2일 때, 사거리가 1, 2인 순서로 탐색한다.

1번과 3번은 궁수와 같은 열이기때문에 제외된다.

모든 궁수에 대해서 공격 대상 탐색이 끝나면 일제히 공격해준다.

 

#include <iostream>
#include <queue>
#include <memory.h>

#define maxsize 15

using namespace std;

int board[maxsize][maxsize];
bool dead[maxsize][maxsize];
bool visit[maxsize][maxsize];
int n, m, d;

void input(){
    cin >> n >> m >> d;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
        }
    }
}
bool isOut(int x, int y){
    if(x < 0 || x == m || y < 0 || y >= n)return true;
    else return false;
}

int archer[3];
int answer;
int dx[3] = {-1, 0, 1};
int dy[3] = {0, -1, 0};

void simulation(){
    int count = 0;
    
    //적들이 밀려온다
    for(int i = n; i > 0; i--){
    	//각 궁수에 대해서 공격 대상 탐색
        vector<pair<int,int>> attack;
        for(int arh = 0; arh < 3; arh++){
            queue<pair<int, int>> q; //x, y;
            memset(visit, false, sizeof(bool)*maxsize*maxsize);
            q.push({archer[arh], i});
            //궁수의 현재 위치 사거리를 계산하기 위해 필요
            int startx = archer[arh];
            int starty = i;
            while(!q.empty()){
                int cx = q.front().first;
                int cy = q.front().second;
                q.pop();
                if(!isOut(cx, cy))visit[cy][cx] = true;
                if(!isOut(cx, cy + n - i) && board[cy][cx] == 1){
                    if(!dead[cy][cx]){
                        attack.push_back({cx, cy});
                        break;
                    }
                    
                }
                for(int dir = 0; dir < 3; dir++){
                    int nx = cx + dx[dir];
                    int ny = cy + dy[dir];
                    int range = abs(nx - startx) + abs(ny - starty);
                    if(isOut(nx, ny) || range > d || visit[ny][nx])continue;
                    else q.push({nx, ny});
                }
            }
        }
        //일제히 공격
        for(auto i : attack){
            if(!dead[i.second][i.first]){
                count++;
                dead[i.second][i.first] = true;
            }
        }
    }
    
    cout << count << "\n";
    answer = max(answer, count);
}

void solve(){
    for(int i = 0; i < m - 2; i++){
        archer[0] = i;
        for(int j = i+1; j < m - 1; j++){
            archer[1] = j;
            for(int z = j+1; z < m; z++){
                archer[2] = z;
                memset(dead, false, sizeof(bool)*maxsize*maxsize);
                simulation();
            }
        }
    }
    cout << answer;
}

int main(){
    input();
    solve();
}