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

dfs를 통해 궁수를 배치 하여 문제를 풀어주는 것이 중요한 문제였습니다.

#include<iostream>
#include<algorithm>
#include<queue>
#include<memory.h>
#include<vector>
using namespace std;
struct sol {
    int x;
    int y;
    int aa;
};
struct cmp {
    bool operator()(sol a, sol b) {
        if (a.aa == b.aa) {
            return a.x > b.x;
 
        }
        return a.aa > b.aa;
    }
};
 
int vv[3];
int N, M, D;
int ans, ans_temp;
int map[20][20];
int map_temp[20][20];
bool v[18];
bool visited[20][20];
queue<sol>q;
priority_queue<sol, vector<sol>, cmp >pq;
sol k;
int finsh, finsh_temp;
int p_x[4] = { 0,1,0,-1 };
int p_y[4] = { -1,0,1,0 };
 
void movee() {
    finsh_temp++;
    for (int Y = N - 1; Y >= 0; Y--) {
        for (int X = 0; X < M; X++) {
            if (map_temp[Y][X] == 1) {
                if (Y + 1 < N) {
                    map_temp[Y + 1][X] = 1;
                    map_temp[Y][X] = 0;
                }
                if (Y + 1 == N) {
                    map_temp[Y][X] = 0;
                }
            }
        }
    }
}
 
void kill() {
    finsh_temp = finsh;
    while (1) { //마지막 병사가 성에 닿으면 끝
        if (finsh_temp == N) break;// 마지막 적군이 사라지면 무한루프 탈출
        for (int i = 0; i < 3; i++) { //궁수 3명 다돌려줌
            while (!q.empty())
                q.pop();
            k.x = vv[i]; k.y = N; k.aa = 0;
            q.push(k);
            memset(visited, false, sizeof(visited));
            while (!q.empty()) {//사거리 까지 dfs돌려줌
                sol cur = q.front();
                q.pop();
                visited[cur.y][cur.x] = true;
                if (cur.aa == D) break;
                for (int dir = 0; dir < 4; dir++) {
                    sol next;
                    next.x = cur.x + p_x[dir];
                    next.y = cur.y + p_y[dir];
                    next.aa = cur.aa + 1;
                    if (next.x > -1 && next.x < M && next.y>-1 && next.y < N && !visited[next.y][next.x]) {
                        if ((map_temp[next.y][next.x] == 3 || map_temp[next.y][next.x] == 1)) {
 
                            visited[next.y][next.x] = true;
                            pq.push(next);
                            q.push(next);
                        } // 병사를 죽일수 있다면
                        else {
 
                            visited[next.y][next.x] = true;
                            q.push(next);
                        }
                    } //범위안이고 방문안했을때
                }// for dir
            }//while 1
            if (!pq.empty()) {
                int k_x = pq.top().x; int k_y = pq.top().y; //가장 가깝고 가장 왼쪽
                map_temp[k_y][k_x] = 3;
            }
            while (!pq.empty())
                pq.pop();
        }//for i
        for (int Y = 0; Y < N; Y++) {
            for (int X = 0; X < M; X++) {
                if (map_temp[Y][X] == 3) {
                    ans_temp++;
                    map_temp[Y][X] = 0;
                }
            }
        }
        movee();//다죽이고 나서
    }//while 1
}
 
void pos(int dep, int start) {
    if (dep == 3) {
        int s = 0;
        for (int i = 0; i < M; i++) { //3마리 배치
            if (!v[i]) continue;
            vv[s++] = i;
        }
 
        for (int Y = 0; Y < N; Y++) {
            for (int X = 0; X < M; X++) {
                map_temp[Y][X] = map[Y][X];
            }
        }
        ans_temp = 0;
        kill();
        ans = max(ans, ans_temp);
        return;
    }
 
    for (int i = start; i < M; i++) {
        if (v[i]) continue;
        v[i] = true;
        pos(dep + 1, i + 1);
        v[i] = false;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> M >> D;
    finsh = N - 1;
    for (int Y = 0; Y < N; Y++) {
        for (int X = 0; X < M; X++) {
            cin >> map[Y][X];
            if (map[Y][X] == 1) {
                finsh = min(finsh, Y);
            }
        }
    }
    ans = 0;
    pos(0, 0);
    cout << ans;
}