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

 

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

 

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

 

---

 

 

해결전략

 

구현 Brute Force, 너비우선탐색 BFS

시뮬레이션 Simulation

 

---

 

 

정답 코드

 

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

// 방향 벡터 (좌, 상, 우)
int dirY[3] = { 0, -1, 0 };
int dirX[3] = { -1, 0, 1 };

int n, m, d;              // 행, 열, 궁수의 공격 거리
int answer;               // 제거할 수 있는 적의 최대 수
vector<int> archers;      // 궁수의 위치
vector<vector<int>> v;    // 초기 적의 위치
vector<vector<int>> Simul;// 시뮬레이션 중에 사용할 배열

int Kill()
{
    int killCnt = 0; // 제거한 적의 수
    vector<pair<int, int>> targets; // 궁수들이 공격할 적들의 위치

    for (int i = 0; i < 3; i++) // 각 궁수별로 가장 가까운 적을 찾는다
    {
        queue<pair<pair<int, int>, int>> Q;
        vector<vector<bool>> ch(n, vector<bool>(m, false));

        Q.push({ { n - 1,archers[i] }, 1 });
        ch[n - 1][archers[i]] = true;

        while (!Q.empty()) {
            int y = Q.front().first.first;
            int x = Q.front().first.second;
            int dist = Q.front().second;
            Q.pop();

            if (dist > d) break;  // 궁수의 공격 거리를 초과
            if (Simul[y][x] == 1) { // 성벽 아래의 적만 탐색
                targets.push_back({ y, x }); // 적을 찾으면 위치를 저장
                break;
            }

            for (int i = 0; i < 3; i++) {
                int ny = y + dirY[i];
                int nx = x + dirX[i];

                if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                if (ch[ny][nx]) continue;

                ch[ny][nx] = true;
                Q.push({ { ny, nx}, dist + 1 });
            }
        }
    }

    // 각 궁수가 찾은 적을 제거
    for (int i = 0; i < targets.size(); i++) {
        int y = targets[i].first;
        int x = targets[i].second;

        if (Simul[y][x] == 1) {
            Simul[y][x] = 0; // 적 제거
            killCnt++;
        }
    }

    return killCnt;
}

bool moveEnemies()
{
    bool bHasEnemies = false; // 적이 남아있는지 여부

    for (int y = n - 1; y >= 0; y--) {
        for (int x = 0; x < m; x++) {
            if (Simul[y][x] == 1)
            {
                Simul[y][x] = 0;

                if (y != n - 1) {
                    Simul[y + 1][x] = 1; // 적을 한 칸 아래로 이동
                }

                bHasEnemies = true; // 적이 남아있음을 표시
            }
        }
    }

    return bHasEnemies;
}

void PlaceArchers(int idx)
{
    if (archers.size() == 3) // 궁수 3명을 배치
    {
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                Simul[y][x] = v[y][x];
            }
        }

        int eliminated = 0; // 제거한 적의 수

        // 적을 제거하고 이동시키는 과정 반복
        while (true) { 
            eliminated += Kill();

            if (!moveEnemies()) break; // 적 이동 후 남아있는 적이 없으면 종료
        }

        answer = max(answer, eliminated); // 최대 제거 수 갱신
        return;
    }

    for (int i = idx; i < m; i++) {
        archers.push_back(i);
        PlaceArchers(idx + 1); // 다음 궁수 배치
        archers.pop_back(); // 백트래킹
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> d;
    v.resize(n, vector<int>(m));
    Simul.resize(n, vector<int>(m));
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            cin >> v[y][x];
        }
    }

    PlaceArchers(0);

    cout << answer;

    return 0;
}

 

 

---