[C++] 백준 17135 - 캐슬 디펜스

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

<풀이>

1. 격자판을 입력받는다.

2. 궁수 3명을 배치해서, 죽일 수 있는 적의 최대 수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 궁수 3명을 배치할 수 있는 모든 경우를 해보아야 합니다. 따라서, 저는 브루트포스를 선택해서 궁수를 모든 경우에 배치해보았습니다.

 

2. 시뮬레이션 구현하기

=> 궁수 3명을 배치한 이후에는 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞게 정확하게 구현하는 것입니다. 구현방법은 아래의 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
struct enemy {
    pos p;
    int dist;
};
 
int N, M, D;
int map[15][15];
int map_copy[15][15];
int archer[3];
int answer;
 
bool cmp(enemy e1, enemy e2) {
    if (e1.dist == e2.dist) {
        if (e1.p.y == e2.p.y) return e1.p.x < e2.p.x;
        return e1.p.y < e2.p.y;
    }
    return e1.dist < e2.dist;
}
 
int getDist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
 
bool isNoEnemy(int col) {
    for (int i = 0; i < col; i++) {
        for (int j = 0; j < M; j++) {
            if (map_copy[i][j] == 1) return false;
        }
    }
    return true;
}
 
void copyMap() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map_copy[i][j] = map[i][j];
        }
    }
}
 
int countDeadEnemy() {
 
    int output = 0;
 
    //1. 시뮬레이션 맵 카피
    copyMap();
    int archerCol = N;
    //2. 시뮬레이션
    while (archerCol >= 1) {
        if (isNoEnemy(archerCol)) break;
        //(1) 모든 궁수마다 죽일 적 선택하기
        vector<pos> kill;
        for (int i = 0; i < 3; i++) {
            vector<enemy> v;
            //적 담기
            for (int j = 0; j < archerCol; j++) {
                for (int k = 0; k < M; k++) {
                    if (map_copy[j][k] == 1) {
                        int dist = getDist(archerCol, archer[i], j, k);
                        if (dist <= D) v.push_back({ {j,k},dist });
                    }
                }
            }
            //정렬
            sort(v.begin(), v.end(), cmp);
            //죽일 적 1명 담기
            if (!v.empty()) kill.push_back(v.front().p);
        }
        //(2) 적 죽이기
        for (auto& k : kill) {
            if (map_copy[k.x][k.y] == 1) {
                map_copy[k.x][k.y] = 0;
                output++;
            }
        }
        //(3) 궁수 라인 올리기
        archerCol--;
    }
 
    return output;
}
 
int selectArcherPos(int idx, int cnt) {
 
    if (cnt == 3) return countDeadEnemy();
 
    int ret = 0;
    for (int i = idx; i < M; i++) {
        archer[cnt] = i;
        ret = max(ret, selectArcherPos(i + 1, cnt + 1));
    }
    return ret;
}
 
void solution() {
    answer = selectArcherPos(0, 0);
}
 
int main() {
    //초기화
    N = 0, M = 0, D = 0;
    memset(map, 0, sizeof(map));
    memset(map_copy, 0, sizeof(map_copy));
    memset(archer, 0, sizeof(archer));
    answer = 0;
 
    //입력
    cin >> N >> M >> D;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

브루트포스와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.