[백준] 17135 - 캐슬 디펜스

DFS, BFS를 모두 사용하지만 결국엔 시뮬레이션이 더 중요한 문제였던듯 하다

1. 궁수의 위치를 DFS를 사용하여 정해준다.

2. 궁수의 위치가 정해졌다면, 기존 map을 tmp_map에 복사하여 시뮬레이션 용 map을 생성

3. 각각의 궁수 위치에서 BFS탐색으로 candi에 조건에 맞는 적의 위치를 저장

4. candi에 저장된 적의 위치를 dist가 가까운 순서, x가 작은 순서대로 정렬한다

5. 한번에 한명의 적을 공격할 수 있기 때문에 candi에 저장된 것이 있다면 맨 앞의 적의 위치면 candi2에 담아준다

6. 각각의 궁수에 대해서 이렇게 탐색을 끝냈다면, tmp_map에 제거할 적의 위치에 적이 있다면 tmp++하고 적을 tmp_map에서 제거

   - 이때 중복되는 적을 공격할 수 있으니 조심하기 바람

7. move함수를 호출하여 적을 아래로 한칸씩 이동시킨다

8. 이 과정을 tmp_map에 적이 한명도 없을때까지 반복한다

9. 최대로 적을 제거할 수 있는 수를 현재 찾은 답과 비교하여 갱신

#include <iostream>
#include <algorithm>
#define MAXSIZE 18
using namespace std;
 
struct QUEUE {
    int x, y, dist;
};
 
int map[MAXSIZE][MAXSIZE];
int tmp_map[MAXSIZE][MAXSIZE];
QUEUE candi2[5];
int dx[] = { -1, 0, 1 };
int dy[] = { 0, -1, 1 };
int N, M, D, dab, candicnt;
 
bool com(const QUEUE i, const QUEUE j) {
    return (i.dist < j.dist) || (i.dist == j.dist && i.x < j.x);
}
 
void bfs(const int x, const int y) {
    QUEUE q[MAXSIZE*MAXSIZE];
    QUEUE candi[MAXSIZE*MAXSIZE];
    int visit[MAXSIZE][MAXSIZE] = { 0 };
    int st, ed, ix, iy, nx, ny, cd;
    st = ed = cd = -1;
    q[++st].x = x; q[st].y = y; visit[y][x] = 1;
    while (st != ed) {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 3; i++) {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N || visit[ny][nx] || (std::abs(nx - x) + std::abs(ny - y)) > D) continue;
            if (tmp_map[ny][nx] == 1) {    candi[++cd].x = nx; candi[cd].y = ny; candi[cd].dist = (std::abs(nx - x) + std::abs(ny - y)); }
            q[++st].x = nx; q[st].y = ny; visit[ny][nx] = 1;
        }
    }
 
    if (cd >= 0) {
        sort(candi, candi + (cd + 1), com);
        candi2[++candicnt].x = candi[0].x;
        candi2[candicnt].y = candi[0].y;
    }
}
 
void move() {
    for (int i = N - 1; i >= 0; i--) 
        for (int j = 0; j < M; j++) {
            if (i == N - 1) tmp_map[i][j] = 0;
            else{
                tmp_map[i + 1][j] = tmp_map[i][j];
                tmp_map[i][j] = 0;
            }
        }
}
 
void mapcopy() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            tmp_map[i][j] = map[i][j];
}
 
bool mapcheck() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (tmp_map[i][j] == 1) return false;
    return true;
}
 
void dfs(int d, int st) {
    if (d == 3) {
        int tmp = 0;
        mapcopy();
        while (1) {
            if (mapcheck()) break;
            candicnt = -1;
            for (int i = 0; i < M; i++)
                if (map[N][i] == 1)    bfs(i, N);
 
            for (int i = 0; i <= candicnt; i++) {
                if (tmp_map[candi2[i].y][candi2[i].x] == 1) {
                    tmp++;
                    tmp_map[candi2[i].y][candi2[i].x] = 0;
                }
            }
            move();
        }
        dab = dab > tmp ? dab : tmp;
        return;
    }
 
    for (int i = st; i < M; i++) {
        map[N][i] = 1;
        dfs(d + 1, i + 1);
        map[N][i] = 0;
    }
}
 
int main(void) {
    cin >> N >> M >> D;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    dfs(0, 0);
    cout << dab << endl;
    return 0;
}