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

 

출력

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

---

접근 방법

• 궁수 배치 경우의 수: 조합을 백트래킹으로 구현(최대15 C 3= 455)
• 캐슬 디펜스: BFS로 턴마다 궁수가 가장 가까운 적이자 왼쪽의 적을 공격 한 후, 적들의 위치를 한 칸씩 내린다.
  • 이때, 궁수는 동시에 공격하며 따라서 같은 적을 쏠 수도 있다. 그럴 경우 1명의 적을 공격한 것으로 카운팅 해줘야 한다.
  • 가장 가까운 적이 여러 명인 경우 가장 왼쪽의 적을 공격하는데 그건, BFS의 탐색을 왼쪽 부터 탐색하게 해주면 된다.
  • set 자료구조를 활용하여 궁수가 한 턴에서 공격한 적을 또 공격하더라도 중복 카운팅이 발생하지 않게 처리.
  • 문제에서 객체들 간 거리는 단순 택시거리.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, d, enemy, ans;
int f[16][16], mat[16][16];
int h[3][2] = { {0,-1},{-1,0},{0,1} };  // 왼쪽 적 우선 공격

vector<pair<int, int>>v, a;

void move() {  // 적이 내려온다.
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 1 && mat[i + 1][j] == 0) {
                mat[i + 1][j] = 1;
                mat[i][j] = 0;
            }
        }
    }
}

void castle() {
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) mat[i][j] = f[i][j];
    }
    int e = enemy;  // 남은 적 수
    int cnt = 0;  // 이 배치에서 죽인 적 수
    while (e) {
        set<pair<int, int>>shoot;  // 두 궁수가 같은 적을 쏠 순 있지만 한명의 적만 죽일 수 있다.
        for (auto i : a) {
            int vis[16][16] = { 0, };
            queue<tuple<int, int, int>>q;  // 궁수 화살의 위치 (y,x)와 현재 이동거리
            q.push({ i.first - 1,i.second, 1 });  // 처음엔 무조건 위로(y-1,x) 좌표로 발사한다.
            vis[i.first - 1][i.second] = 1;
            while (q.size()) {
                int y = get<0>(q.front());
                int x = get<1>(q.front());
                int c = get<2>(q.front());
                q.pop();
                if (mat[y][x] == 1) {
                    shoot.insert({ y,x });  // 이번 턴에 죽을 적
                    break;
                }
                if (c == d)  // 더이상 적에게 닿지 않는 화살이므로
                    continue;
                for (int i = 0; i < 3; i++) {
                    int yy = y + h[i][0];
                    int xx = x + h[i][1];
                    if (yy < 0 || xx >= m || xx < 0)
                        continue;
                    if (vis[yy][xx]) continue;
                    q.push({ yy,xx,c + 1 });
                }
            }
        }
        for (auto i : shoot) {
            mat[i.first][i.second] = 0;
            e--;  // 남은 적 감소
            cnt++;  // 공격한 적 카운팅
        }
        for (int i = 0; i < m; i++) {
            if (mat[n - 1][i] == 1) {  // 죽지 않고 성에 도달한 적 제거 (카운팅 X)
                e--;
                mat[n - 1][i] = 0;
            }
        }
        move();
    }
    ans = max(ans, cnt);
}

void bt(int cnt, int s) {  // 백트래킹으로 모든 궁수 자리 검사
    if (cnt == 3) {
        castle();
        return;
    }
    for (int i = s; i < m; i++) {
        a.push_back({ v[i].first,v[i].second });
        bt(cnt + 1, i + 1);
        a.pop_back();
    }
}

void solve() {
    bt(0, 0);
    cout << ans;
}

void input() {
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> f[i][j];
            if (f[i][j] == 1) enemy++;
        }
    }
    for (int i = 0; i < m; i++) v.push_back({ n,i });
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

푸는데 도움을 받은 반례 (질문게시판 반례)

1. 왼쪽 적 우선 공격

5 5 2
1 0 1 1 1
0 1 1 1 1
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1

ans: 14

 

2.

10 10 8
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

ans: 30

 

3. 종료조건 확인

2 4 2
1 1 1 1
0 1 1 0

ans: 5

 

4. 왼쪽 적 우선 공격

9 10 4
1 0 0 1 0 1 0 1 1 0
0 0 0 1 0 0 0 1 0 0
0 1 0 0 1 0 0 1 1 1
0 0 1 1 0 1 0 1 1 0
0 1 1 0 0 0 0 1 0 1
0 1 1 1 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0 0
1 1 1 1 1 1 1 1 0 1
0 1 1 0 1 1 0 1 1 0

ans: 26

---

마무리

• 백트래킹 + BFS로 시뮬레이션 하는 문제
• 전체 시간 복잡도: O(M³) × O(N × (D² + N×M)) ≈ 2,218,125