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

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

궁수 세 명을 최적의 위치에 배치해서, 가장 많은 적을 죽이도록 하는 문제이다.

따라서 열의 길이를 이용해서, 궁수가 위치할 수 있는 세 곳을 먼저 조합으로 뽑는다.

각각의 궁수에 대해 bfs를 돌린다. 앞에서부터 멀리있는 곳까지 확인할 것이다.

이때 중요한 것이 몇가지 있다.

궁수들은 같은 거리라면 왼쪽에 있는 적부터 공격한다. 따라서 bfs를 수행할 때, 탐색의 순서를 좌, 상, 우 이렇게 해줘야 한다.

또한 궁수들은 동시에 같은 적을 공격할 수 있다고 했기 때문에, 하나의 궁수를 가지고 탐색을 하다가 적을 발견했을 때에, 바로 그 적을 없애면 안 된다.

그걸 없애버리면 동시에 같은 적을 공격할 수 있다는 조건에 위배되기 때문이다.

set에 추가만 해주고, 이번 턴에 죽일 적을 찾았으므로, 바로 현재 궁수의 bfs를 종료해주면 된다.

세 궁수의 탐색이 사정거리만큼 모두 이루어지고 나면 set을 활용해서 지도에서 적을 지우고, set을 비워준다.

시기적절하게 초기화를 해주고, 적들을 지도에서 제거하고, 적들을 이동시키는 잔처리가 중요한 문제였다.

#include<iostream>
#include<queue>
#include<set>
using namespace std;
typedef pair<int, int> pii;
int m[19][18], tmp[19][18], N, M, d, st = 1, arr[19], dis[19][18];
int dr[3] = { 0,-1,0 }, dc[3] = {-1, 0, 1};
bool isused[18];
queue<pii> q;
set<pii> killed;
 
void bfs(pii start) {
    dis[start.first][start.second]++;
    q.push(start);
    while (!q.empty()) {
        pii cur = q.front(); q.pop();
        if (dis[cur.first][cur.second] >= d) continue; //사정거리 마지막 점
        for (int i = 0; i < 3; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] >= 0) continue;
            if (m[nr][nc] == 1) {
                killed.insert({ nr, nc });
                return;
            }
 
            q.push({ nr, nc });
            dis[nr][nc] = dis[cur.first][cur.second] + 1;
        }
    }
}
void init() {
    for(int i = 1 ; i <= N+1 ; i++)
        for(int j = 1 ; j <= M ; j++)
            dis[i][j] = -1;
    while (!q.empty()) q.pop();
}
bool allKilled() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) 
            if (m[i][j] != 0) 
                return false;
        
    return true;
}
int kill() {
    int cnt = 0;
    for (set<pii>::iterator itr = killed.begin(); itr != killed.end(); itr++) {
        m[itr->first][itr->second] = 0;
        cnt++;
    }
    killed.clear();
    return cnt;
}
void move() {
    for (int i = N; i >= 1; i--) 
        for (int j = 1; j <= M; j++) 
            m[i][j] = m[i - 1][j];
}
int ans = 0;
void btk(int k) {
    if (k == 3) {
        
        int killSum = 0;
        while (1) {
            //적 다 사라질 때까지
            if (allKilled()) break;
 
            for (int i = 0; i < 3; i++) {
                bfs({ N + 1, arr[i] });
                init();
            }
            killSum += kill();//죽은 적들 배열에서 제거
        
            move();    
        }
        if (ans < killSum) ans = killSum;
        
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                m[i][j] = tmp[i][j];
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i <= M; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            btk(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> N >> M >> d;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    btk(0);
    cout << ans;
    return 0;
}