[Algorithm] BOJ 17135 캐슬 디펜스

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

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

출력

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

예제

---

풀이

---

생각

• 조건이 많다.
  • 궁수 3명을 배치하는데 M개의 공간 중 3개를 배치하는 경우의 수를 순회해야 한다.
  • 적과 궁수의 거리를 계산하면서, 거리가 D 이하이면서 최소인 적을 찾아내야 한다.
  • 거리가 같은 적이 여럿인 경우, 가장 왼쪽의 적을 공격한다.
  • 여러 궁수가 한 적을 공격할 수 있다.
  • 턴마다 적은 아래로 내려온다.
  • 적이 없어지면 종료한다.
• 먼저 자료구조를 무엇을 쓸까 고민하다가 굳이 맵 전체를 저장하지 말고 적 위치만 저장해서 업데이트하면 되지 않을까 생각했다. 거리를 계산한다던가, 적을 이동시킨다던가 하는 연산에서는 문제가 없었다. 하지만 적을 공격하면 적을 삭제하는 과정이 있어야 했는데, 처음에 vector로 위치를 저장하자니 데이터를 삭제하는게 매우 귀찮다고 생각했다.
• 그리고 문제는 여러 궁수가 한 적을 공격하는 경우에 현재 턴에서 앞 궁수가 내가 공격할 적을 공격했다면 현재 내가 타겟팅하고 있는 인덱스의 적은 다른 적이 되어(vector가 삭제되면 앞으로 당겨지니깐) 문제가 생길 것이라 생각했다.
  • 이 과정에서 그럼 list로 해볼까 했는데 똑같다. 특정 위치의 list 데이터가 사라지면 기존 iterator로 가르키고 있는 공간이 없어지기 때문에 접근하면 오류가 난다.
• 아무튼 그래서 그냥 전체 맵을 저장하고 순회하기로 했다. 맵이 크지도 않고 최대 15밖에 되지 않으므로 순회해도 오래 걸리지 않을 것이라고 생각했다.

방법

• 먼저 m개 중 3개의 궁수 위치를 뽑는다(조합).

  • vector와 prev_permutation 활용
  • 궁수 위치 저장 -> present 변수

• 궁수마다 최적의 공격대상(D이하 최소거리, 제일 왼쪽)을 찾는다.

  • checking 함수 -> min_enemy 변수

• 최적의 공격대상을 공격한다.

  • kill 함수 -> 맵에 적(1)을 없앤다(0)
  • 이번 턴의 앞 궁수가 죽였음을 확인하기 위해 최적의 공격대상이 아직 있는가를 확인하고 죽인다.

• 적들을 한 번 앞으로 움직인다.

  • move 함수

• 최적의 공격대상을 찾으면서 전체 적을 카운트(enemynum)하고, 공격하면서 죽인 적의 수(killnum)를 확인한다. 그리고 다음 순번에 앞으로 넘어가서 맵을 넘어가버리는 없어지는 적들의 수(gonenum)도 확인한다. 이 3개의 데이터를 활용하면 현재 맵에 적이 있는지 없는지를 확인할 수 있다. 이것으로 종료 조건을 만들어준다.

• 위 과정 checking, kill, move를 적이 없어질 때까지 반복한다.

• kill을 수행하고 죽인 적의 수를 저장해놓으면, 현재 궁수위치에서 죽일 수 있는 수를 계산할 수 있다. 전체 궁수 위치들을 돌아가면서 이 값들의 최대값을 찾는다.

유의

• 오리지널 값을 유지해야하는 곳이 있다.
  • 전체 맵은 궁수 위치가 바뀔 때마다 기존의 값 그대로 유지되야 한다. 고로, 오리지널 값을 유지하면서 계속 copy해주어야 한다.
• 현재 위치의 궁수와 공격할 적의 위치/걸리를 다른 자료형으로 구분하여 풀었는데, 사실 이를 하나의 struct로 풀어도 괜찮을 것 같다. 문제가 푸는데 좀 길어지다 보니깐 둘의 자료형이 헷갈렸다.

---

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct enemy {
    int x, y, dis;
};
int n, m, d;
int orip[17][17], p[17][17];
int dis;
vector<int> archer;
vector<pair<int, int>> present(3);
enemy min_enemy[3];

void checking(int& enemynum) {
    enemynum = 0;
    min_enemy[0] = { -1, -1, 100 };
    min_enemy[1] = { -1, -1, 100 };
    min_enemy[2] = { -1, -1, 100 };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (p[i][j] == 0) continue;
            ++enemynum;
            for (int k = 0; k < 3; ++k) {
                dis = abs(present[k].first - i) + abs(present[k].second - j);
                if (dis > d) continue;    // 최소거리 넘으면
                if (min_enemy[k].dis == dis && min_enemy[k].y < j) continue;    // 가장 왼쪽값 아니면
                if (min_enemy[k].dis >= dis) min_enemy[k] = { i, j, dis };
            }
        }
    }
}
void kill(int& killnum) {
    killnum = 0;
    for (int i = 0; i < 3; ++i) {
        if (min_enemy[i].x < 0) continue;
        if (p[min_enemy[i].x][min_enemy[i].y] == 0) continue; // 앞 궁수가 미리 죽인 것
        p[min_enemy[i].x][min_enemy[i].y] = 0; // kill
        killnum++;
    }
}

void move(int& gonenum) {
    gonenum = 0;
    int tmp[17] = { 0, }, gone = 0;
    for (int i = 0; i < n; ++i) {
        swap(tmp, p[i]);
    }
    for (int i = 0; i < m; ++i)
        gone += p[n - 1][i];
}

int main() {
    cin >> n >> m >> d;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> orip[i][j];
    archer.push_back(1);
    archer.push_back(1);
    archer.push_back(1);
    while (archer.size() < m) {
        archer.push_back(0);
    }

    int res = 0;
    do {
        copy(&orip[0][0], &orip[0][0] + (17 * 17), &p[0][0]);
        for (int i = 0, ind = 0; i < m; ++i) {
            if (archer[i] == 1) {
                present[ind] = { n, i };
                ind++;
            }
        }
        int num = 0, enemynum, killnum, gonenum;
        while (true) {
            checking(enemynum);
            kill(killnum);
            move(gonenum);
            num += killnum;

            if (enemynum - (killnum + gonenum) == 0)
                break;
        }
        res = max(res, num);
    } while (prev_permutation(archer.begin(), archer.end()));

    cout << res << '\n';
    return 0;
}    

---

느낀점

• 조건이 많아서 생각을 정리하는데 오래 걸렸다. 시간제한이 있었다면 사실 시간제한 안에 못풀었을 것 같다.
  • 문제를 보고, 문제를 쪼갤 수 있는 능력을 길러야할 것 같다. 함수모듈(?)식으로 쪼개서 풀어낼 수 있게. 구조들을 빨리 생각해낼 수 있는 연습으로.
• 자료형에 대한 부족한 이해를 한번 더 느꼈다.
  • vector, list를 사용할까 고민했는데 이 때 데이터 삭제에 대해 하는 법과 삭제한 부분에 접근하면 어떻게 되는가를 미리 잘 알고 있었더라면 더 빨리 풀 수 있었을 것.
  • copy 함수를 활용하면서 2차원 배열의 복사 하는법을 부족하게 알 고 있던 것을 느꼈다.

---

참조

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