백준 17135 캐슬 디펜스 (C++)

17135번: 캐슬 디펜스

구현 문제이다. 아래 알고리즘이 복잡해 보이지만 크게 3가지 단계의 반복으로 볼 수 있다.

1. 궁수 3명을 배치한다.
2. 궁수를 기준으로 D 거리 안의 적을 왼쪽부터 공격한다.
3. 적이 한칸 앞으로 온다. 이 때 N-1 위치에 있는 적은 사라진다.

궁수 3명을 배치하는 과정은 dfs() 함수로 나타냈다. 배치가 끝나면 kill()과 goEnemy() 함수를 반복하며 count를 더해 제거한 적 수를 저장해주었다. kill() 함수에서는 bfs를 사용하여 D 거리 안에 있는 적을 제거하였다. 여기서 주의할 점은 궁수는 같은 적을 공격할 수 있다는 점이다. 그래서 적을 발견한 시점에서 바로 제거하지 않고 zero 벡터에 저장해 준 후 모든 궁수의 범위 내의 적을 구하면 그 후에 반복문을 돌며 제거해주면서 카운트해주었다. goEnemy() 함수에서는 만약 모든 적이 제거되었다면 false를 리턴하여 반복문을 끝내고, 적이 존재하면 한 칸 앞으로 이동시켜준다. 이를 반복하며 최대로 제거한 적의 수를 구해 출력해주었다.
생각보다 오래 걸린 문제였다. 중간 중간 오타와 잘못된 문제 이해로 인해 시간 낭비가 많았다. 주의하자.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

int N, M, D, res = 0;
vector<int> v;
int A[15][15];
int B[15][15];

int kill() {
    int count = 0;
    int dy[3] = { 0, -1, 0 };
    int dx[3] = { -1,0,1 };
    vector<pair<int, int>> zero;

    for (int k = 0; k < 3; k++) {
        queue<pair<pair<int, int>, int>> q;
        bool check[15][15];

        memset(check, 0, sizeof(check));

        q.push({ { N - 1,v[k] },1 });
        check[N - 1][v[k]] = true;

        while (!q.empty()) {
            int y = q.front().first.first;
            int x = q.front().first.second;
            int c = q.front().second;

            q.pop();

            if (c > D) break;
            if (B[y][x] == 1) {
                zero.push_back({ y,x });
                break;
            }

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

                if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                if (check[ny][nx]) continue;

                check[ny][nx] = true;
                q.push({ { ny,nx }, c + 1 });
            }
        }
    }

    for (int i = 0; i < zero.size(); i++) {
        int y = zero[i].first;
        int x = zero[i].second;

        if (B[y][x] == 1) {
            B[y][x] = 0;
            count++;
        }
    }

    return count;
}

bool goEnemy() {
    bool tf = false;

    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < M; j++) {
            if (B[i][j] == 1) {
                B[i][j] = 0;

                if (i != N - 1) {
                    B[i + 1][j] = 1;
                }

                tf = true;
            }
        }
    }

    return tf;
}

void dfs(int depth) {
    if (v.size() == 3) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                B[i][j] = A[i][j];
            }
        }

        int count = 0;

        while (1) {
            count += kill();
            
            if (!goEnemy()) break;
        }

        res = max(res, count);

        return;
    }

    for (int i = depth; i < M; i++) {
        v.push_back(i);
        dfs(depth + 1);
        v.pop_back();
    }
}

void solution(){
    dfs(0);

    cout << res;
}

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

    cin >> N >> M >> D;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}