← All Articles

[BAEKJOON] 17135. 캐슬 디펜스

Posted on

문제 :

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

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


입력 :

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.


출력 :

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



풀이 :

오랜만에 구현 문제를 푼 것 같다.

이 문제는 구현 양이 많아서 로직부터 차근차근 설계한 후에 코딩을 시작해야 문제에 접근하기 쉬운 문제인 것 같다.

문제 접근 순서는 다음과 같다.

  1. 3명의 궁수 위치 결정 → 재귀 방식을 통한 열 인덱스 중 3개를 선택하는 조합 방식으로 구현
  2. 각 궁수별 공격 위치 탐색 → BFS 탐색 활용. 여기서 주의할 점은 가장 가까이 위치한 적이 여러 명이면 맨 왼쪽 위치의 적을 공격하도록 우선순위 큐로 구현함.
  3. 공격 위치들 중에 중복되지 않고 공격 받는 적의 명수 카운트
  4. 아직 살아 있는 적이 있다면 한 칸씩 적들의 위치를 내린 후 1번부터 반복


코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>

#define pii pair<int, int>

using namespace std;
typedef struct PQnode {
    int x, y, dist;
} PQnode;

struct compare {
    bool operator()(PQnode a, PQnode b) {
        if (a.dist == b.dist)
            return a.y > b.y;
        return a.dist > b.dist;
    }
};

int orgmap[15][15], map[15][15], di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0}, n, m, maxdist, orgenemy, answer;
bool selected[15];

pii bfs(int x, int y) {
    bool visit[15][15]{false};
    priority_queue<PQnode, vector<PQnode>, compare> pq;
    pq.push(PQnode{x, y, 1});
    visit[x][y] = true;

    while (!pq.empty()) {
        int curx = pq.top().x, cury = pq.top().y, curd = pq.top().dist;
        pq.pop();
        if (map[curx][cury]) return pii(curx, cury);
        if (curd == maxdist) continue;

        for (int k = 0; k < 4; k++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if (0 > cmpx || cmpx >= n || 0 > cmpy || cmpy >= m) continue;
            if (visit[cmpx][cmpy]) continue;
            pq.push(PQnode{cmpx, cmpy, curd + 1});
            visit[cmpx][cmpy] = true;
        }
    }
    return pii(-1, -1); // 적이 근방에 없는 경우
}

void checkMaxEnemy() {
    queue<pii > attackq;
    vector<int> archers;
    int attackablecnt = 0, i, enemynum = orgenemy;

    for (i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            map[i][j] = orgmap[i][j];

    for (i = 0; i < m; i++)
        if (selected[i]) archers.push_back(i);

    while (enemynum) {
        for (i = 0; i < 3; i++) {
            pii loc = bfs(n - 1, archers[i]);
            if (loc.first == -1) continue;
            attackq.push(loc);
        }   // 각 궁수별 공격 위치 탐색

        while (!attackq.empty()) {
            int atkx = attackq.front().first, atky = attackq.front().second;
            attackq.pop();
            if (map[atkx][atky]) {
                map[atkx][atky] = 0;
                attackablecnt++;
                enemynum--;
            }
        }   // 공격위치 공격하고 갯수세기

        for (i = 0; i < m; i++)
            if (map[n - 1][i]) enemynum--;

        if (enemynum) {
            for (i = n - 2; i >= 0; i--)
                for (int j = 0; j < m; j++)
                    map[i + 1][j] = map[i][j];
        }
        for (i = 0; i < m; i++)
            map[0][i] = 0;
        // 한 줄씩 적 위치 내리기
    }
    answer = max(answer, attackablecnt);
}

void selectlocation(int cur, int count) {
    if (count == 3) {
        checkMaxEnemy();
        return;
    }
    if (cur == m) return;
    selected[cur] = true;
    selectlocation(cur + 1, count + 1);
    selected[cur] = false;
    selectlocation(cur + 1, count);
}


int main() {
    cin >> n >> m >> maxdist;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> orgmap[i][j];
            if (orgmap[i][j]) orgenemy++;
        }
    selectlocation(0, 0);
    cout << answer << '\n';
    return 0;
}


AlgorithmalgorithmbaekjoonC++