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

문제 이해 단계

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

17135번: 캐슬 디펜스

NxM맵에 적이 배치되어 있다.
그리고 궁수는 무조건 NxM 맵 밖에 있는 N+1 위치에 3명만 존재한다.

N+1 위치는 성의 위치이기도 하다. 
하나의 칸에는 무조건 한 명이 궁수만 존재할 수 있다.

궁수는 사거리가 D 이하인 적들만 없앨 수 있다.

궁수 3명은 무조건 동시에 공격을 하며, 같은 적을 공격할 수도 있다.
공격당한 적은 게임에서 제외된다.

적을 선정하는 기준은 궁수에게 거리가 가까운 적,
그런 적이 여러 명이라면 가장 왼쪽에 있는 적을 선정한다.

공격이 끝나면 모든 적은 아래로 한 칸 이동한다.
적군이 성(N+1)에 도달하면 게임에서 제외된다.

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

해당 조건에서 궁수를 적절히 배치했을 때
가장 많이 없앨 수 있는 적의 수를 구하는 문제.

 

---

문제 접근 단계

늘 그렇듯, 이 문제의 제한사항부터 살펴봐야 한다. 

맵의 크기인 N, M이 최대 15까지이다.

매번 적의 위치를 새로 구해도 15x15를 벗어나지 않기 때문에
적의 위치를 구하는 것은 그다지 시간을 잡아먹지 않는다.

또한 궁수의 배치를 생각해 보면,
궁수는 무조건 3명에 무조건 성의 위치(N+1) 행에 배치해야 한다.

즉, 바뀌는 것은 M의 위치일 뿐이므로
3중 반복으로 일일이 계산해도 시간이 얼마 걸리지 않는다.

위의 말을 종합해 보면
궁수의 위치에 따른 시뮬레이션을 돌리는 것은 브루트포스로 충분하다는 소리이다.

---

동시에 같은 적 공격 가능

해당 문제에서의 특징은 이 부분인 것 같다.

동시에 같은 적을 공격 가능하다는 뜻은 
한 턴마다 무조건 적 3명이 제거되는 것이 아닐 수도 있다는 뜻이다.

즉, 이미 공격한 적을 또다시 공격할 수도 있기 때문에,
코드 상으로 처리해 줄 때 골치 아플 수도 있다.

이 부분을 신경 써주면서 구현을 해줘야 할 것 같다.

---

제거할 적을 선정

궁수와 적 사이의 거리를 계산해서
거리가 가까운 적을 찾는 것은 그렇게 어려운 일이 아니다.

문제는 거리가 동일한 적이 여러 명일 때 나타난다.

해당 문제에서는 그럴 때
가장 왼쪽에 있는 적을 제거 대상으로 선정했는데,

거리가 같은 적을 담는 동시에 좌표상 가장 왼쪽에 있는 적을
선정하기 위해서는 정렬을 사용해야 한다.

이 부분에 대해서는 코드 구현 단계에서 설명하겠다.

---

적 움직이기

이 부분은 그냥 원래 위치에서 행 위치를 +1을 해주는 게 끝이긴 한데,

주의가 필요한 것은 순차적으로 아래로 내리다 보면 이전 좌표가 지워질 수 있기 때문에,
맵을 복사 해서 새로운 곳에 그린 다음 원래 맵에 복사하는 것이 편하다는 것이다.

이게 말로 해서 무슨 소리인지 모르겠으니까
또 그냥 코드 구현단계에서 설명하겠다.

 

---

문제 구현 단계

// 좌표 구조체
struct Point{
    int x;
    int y;
};

vector<Point> enemy; // 적군 좌표
int map[17][17] = {0,};
int N,M,D; // 입력


// 적 위치 업데이트
bool updateEnemy(){
    bool remain = false;
    vector<Point> newEnemy;
    newEnemy.reserve(N*M);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 1){
                remain = true; // 한마리라도 있으면 true
                newEnemy.push_back({i,j});
            }
        }
    }
    enemy = newEnemy; // 새로운 위치 vector 적용
    return remain;
}

적이 존재하는지를 확인함과 동시에 위치를 갱신하는 updateEnemy함수이다.

Point라는 좌표 구조체를 만듦으로써,
적군 좌표를 저장하는 벡터 enemy를 만들었다.

함수는 그냥 전체 맵을 훑어서 적을 의미하는 1이 하나라도 있으면
적이 있음을 의미하는 remain을 true로 만들고, 
그 적군의 좌표를 newEnemy 벡터에 담는다.

반복문이 종료되면 그렇게 만든 newEnemy 정보를
enemy로 대체시킴으로써 갱신시킨다.

반환값은 remain인데 이는 적군이 남아있는지 아닌지를 판단하기 위함이다.
true면 남아있는 것, false면 한 명도 없는 것이다.

// 정렬 기준
bool compare(Point a, Point b){
    return a.y < b.y;
}

// 궁수 공격 함수
int attack(int arr[]){
    int kill = 0; // 죽은 적군 수

    // i = 각 궁수
    for(int i = 0; i < 3; i++){
        int min_dist = 9999;
        vector<Point> tmp; // 제거 대상 후보
        for(int j = 0; j < enemy.size(); j++){
            int dist = abs(N+1-enemy[j].x)+abs(arr[i]-enemy[j].y); // 거리 계산
            
            // 해당 적군의 거리가 지금까지의 최소 거리보다 작을 때
            if(dist < min_dist){
                min_dist = dist;
                tmp.clear(); // 지금까지의 제거 대상 후보 초기화
                tmp.push_back({enemy[j].x,enemy[j].y}); // 후보 리스트에 추가
            }
            // 최소 거리와 같을 때
            else if(dist == min_dist){
                tmp.push_back({enemy[j].x,enemy[j].y}); // 후보 리스트에 추가
            }
        }
        sort(tmp.begin(),tmp.end(),compare); // 정렬 기준에 따라 정렬
        int dist = abs(N+1-tmp[0].x) + abs(arr[i]-tmp[0].y); // 최우선에 있는 적

        // 사정거리 D안에 있고, 그 적이 아직 제거안됐을 때
        if(dist <= D && map[tmp[0].x][tmp[0].y] == 1) 
        {
            map[tmp[0].x][tmp[0].y] = 0; // 적군 제거
            kill++; // 제거수 + 1
        }
    }
    return kill;
}

각 궁수가 적을 공격하는 attack함수이다.
매개변수로 궁수의 열 위치를 나타내는 arr 배열을 받는다.

반복문 가장 바깥에 있는 i는 arr [i]이며, 각 궁수를 나타낸다.

거리가 가장 짧은 dist를 찾기 위해,
적의 좌표가 담겨있는 enemy 벡터를 탐색하여 거리를 계산한다.

그리고 거리가 최소인 것의 enemy 좌표 정보를
tmp라는 제거 대상 후보 벡터에 이를 담는다.

그 과정에서 만약 더 작은 거리 값이 나타나면
그 tmp벡터를 초기화하고 그 값을 담는다.

이렇게 값 담기가 완료되면
그 안에 담겨있는 값을 만들어둔 정렬기준 compare에 따라 정렬한다.

우리가 선정해야 하는 것은 최우선순위이기 때문에
당연히 가장 앞에 있는 tmp [0]인 적군이다.

그래서 해당 적군과의 거리를 계산하고 이 값이 D 이하인지 확인해야 한다.

여기서 해당 값이 1인지 확인해 주는 이유는
궁수들이 동일한 적을 쏠 수 있어, 해당 적이 이미 제거됐을 수 있기 때문이다.

그렇기 때문에 아직 살아있는 경우에만 kill+1일 해주기 위해서이다.

이런 경우에만 해당 map 좌표를 0으로 만들어주고 kill+1을 해준다.
반환값을 kill을 리턴해준다.

// 적군 움직이는 함수
void move(){
    // 죽은거 제외하고 나머지 적군들 업데이트
    updateEnemy();
    int cmap[17][17] = {0,}; // 맵 복사
    for(int i = 0; i < enemy.size(); i++){
        if(enemy[i].x + 1 == N+1) continue; // 성에 도달한건 새로운 맵에 안담음
        cmap[enemy[i].x+1][enemy[i].y] = 1; // x+1로 전진
    }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) map[i][j] = cmap[i][j]; // 새로운 맵을 원래 맵으로
}

적군을 아래로 움직이는 move 함수이다.

일단 attack 뒤에 호출될 것이기 때문에
죽은 적을 제외하고 남아있는 적군들만 움직여야 한다.

그것을 위해 updateEnemy를 호출하여 새로운 적 정보를 갱신해 준다.

이후 한 칸씩 내려주는데,
아까 언급했던 것처럼 새로운 맵을 생성 하여 그곳에 움직인 값을 만들어준다.

이렇게 해주는 이유는 값이 덮어써지는 것을 막기 위해서이다.

// 궁수가 해당 배치일 때 시뮬레이션 돌리는 함수
int setting(int arr[]){

    int ans = 0;
    // 적이 없을때까지 반복
    while(updateEnemy()){
        ans += attack(arr);
        move();
    }
    return ans;
}

전체적인 컨트롤을 담당하는 setting함수이다.
매개변수로 궁수의 y값 배치를 나타내는 arr []이 들어간다.

위 로직은 간단하게 적이 없을 때까지
updateEnemy를 실행하고 attack과 move를 반복하는 것이다.

최종적으로 반환하는 것은 kill을 계속 더한 ans를 반환하는 것이다.

여기까지가 핵심함수의 설명의 끝이고, 나머지는 메인함수이다.
이는 주석으로 충분히 설명이 가능할 것이라고 생각한다.

그래서 아래에 전체 코드에 대해서 올리고 설명을 끝내겠다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

// 좌표 구조체
struct Point{
    int x;
    int y;
};

vector<Point> enemy; // 적군 좌표
int map[17][17] = {0,};
int N,M,D;

// 정렬 기준
bool compare(Point a, Point b){
    return a.y < b.y;
}

// 적 위치 업데이트
bool updateEnemy(){
    bool remain = false;
    vector<Point> newEnemy;
    newEnemy.reserve(N*M);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 1){
                remain = true; // 한마리라도 있으면 true
                newEnemy.push_back({i,j});
            }
        }
    }
    enemy = newEnemy; // 새로운 위치 vector 적용
    return remain;
}

// 궁수 공격 함수
int attack(int arr[]){
    int kill = 0; // 죽은 적군 수

    // i = 각 궁수
    for(int i = 0; i < 3; i++){
        int min_dist = 9999;
        vector<Point> tmp; // 제거 대상 후보
        for(int j = 0; j < enemy.size(); j++){
            int dist = abs(N+1-enemy[j].x)+abs(arr[i]-enemy[j].y); // 거리 계산
            
            // 해당 적군의 거리가 지금까지의 최소 거리보다 작을 때
            if(dist < min_dist){
                min_dist = dist;
                tmp.clear(); // 지금까지의 제거 대상 후보 초기화
                tmp.push_back({enemy[j].x,enemy[j].y}); // 후보 리스트에 추가
            }
            // 최소 거리와 같을 때
            else if(dist == min_dist){
                tmp.push_back({enemy[j].x,enemy[j].y}); // 후보 리스트에 추가
            }
        }
        sort(tmp.begin(),tmp.end(),compare); // 정렬 기준에 따라 정렬
        int dist = abs(N+1-tmp[0].x) + abs(arr[i]-tmp[0].y); // 최우선에 있는 적

        // 사정거리 D안에 있고, 그 적이 아직 제거안됐을 때
        if(dist <= D && map[tmp[0].x][tmp[0].y] == 1) 
        {
            map[tmp[0].x][tmp[0].y] = 0; // 적군 제거
            kill++; // 제거수 + 1
        }
    }
    return kill;
}

// 적군 움직이는 함수
void move(){
    // 죽은거 제외하고 나머지 적군들 업데이트
    updateEnemy();
    int cmap[17][17] = {0,}; // 맵 복사
    for(int i = 0; i < enemy.size(); i++){
        if(enemy[i].x + 1 == N+1) continue; // 성에 도달한건 새로운 맵에 안담음
        cmap[enemy[i].x+1][enemy[i].y] = 1; // x+1로 전진
    }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) map[i][j] = cmap[i][j]; // 새로운 맵을 원래 맵으로
}

// 궁수가 해당 배치일 때 시뮬레이션 돌리는 함수
int setting(int arr[]){

    int ans = 0;
    // 적이 없을때까지 반복
    while(updateEnemy()){
        ans += attack(arr);
        move();
    }
    return ans;
}

// 원래 맵으로 초기화
void reset(int origin[17][17]){
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) map[i][j] = origin[i][j];
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> D;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) enemy.push_back({i,j});
        }

    int origin[17][17];
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) origin[i][j] = map[i][j];
    int ans = 0;
    // 삼중 반복문으로 모든 궁수 배치 경우의 수
    for(int i = 1; i <= M-2; i++){
        for(int j = i+1; j <= M-1; j++){
            for(int k = j+1; k <= M; k++){
                reset(origin); // 할때마다 초기화
                int arr[3] = {i,j,k};
                int val = setting(arr);
                ans = max(ans,val); // 최대값
            }
        }
    }
    cout << ans;
}

 

---

시행착오

빡구현 문제였던 것 같다. 하루종일 풀었던 것 같다.

푸는 건 그렇게 막 오래 걸리진 않았던 것 같은데,
문제를 잘못 읽어서 정렬 기준을 잘못 세워서 고생했다.

이 문제가 코테에 나와서 1시간 안에 풀라면 못 풀 것 같다.
그래도 어느 정도 풀 수 있다는 게 다행인 건가?

이건 정답을 봐도 결국 구현문제라서
답을 보는 게 의미가 없는 것 같아서 안 봤다.