백준 17135번 캐슬 디펜스

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include <algorithm>
#include <cstring> //memset
#include<tuple>
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
const ll MAX = 1000000000;
const int INF = 87654321;
int N, M, D;
 
int arr[20][20];
int carr[20][20];
int dy[3] = { 0,-1,0 };
int dx[3] = { -1,0,1 };
int visited[20][20];
int check[20][20];
int ans = 0;
vector<int> arc;
void copy() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            carr[i][j] = arr[i][j];
}
void reset() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            visited[i][j] = 0;
}
 
void resetChk() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            check[i][j] = 0;
}
 
//궁수 화살쏴서 적 몇명잡는지 체크
void BFS() {
    copy();
    resetChk();
    int pos = N;
    
    while (pos >= 1) {
        for (int i = 0; i < arc.size(); i++) {
            reset();
            queue< pii> q;
            q.push({ pos - 1,arc[i] });
 
            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;
                q.pop();
                visited[y][x] = 1;
 
                //만약 사격거리안에서 적이발견되면 쏜다.
                if (carr[y][x] == 1) {
                    check[y][x] = 1;
                    break;
                }
 
                for (int j = 0; j < 3; j++) {
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    if (0 <= ny && ny < N && 0 <= nx && nx < M && abs(arc[i] - nx) + abs(pos - ny) <= D && !visited[ny][nx]) {
                        q.push({ ny,nx });
                    }
                }
            }
        }
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (check[i][j]) {
                    carr[i][j] = 0;
                }
 
        pos--;
    }
    int ret = 0;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (check[i][j])
                ret++;
 
 
 
    ans = max(ans, ret);
}
 
//궁수 위치 3개 고르기
void DFS(int pos, int cnt) {
    if (cnt > 3) return;
    if (cnt == 3) {
        BFS();
        return;
    }
    if (pos >= M) return;
 
    arc.push_back(pos);
    DFS(pos + 1, cnt + 1);
    arc.pop_back();
    DFS(pos + 1, cnt);
 
}
 
int main(void) {
    cin >> N >> M >> D;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    
    DFS(0, 0);    
 
    cout << ans;
}
 
 
 
 
 

처음문제 풀때 접근을 병사들이 공격할때 좌표를 내리는 식으로 구현했었는데,

궁수들이 올라가는방식이 구현하기 훨씬 쉽네요. 

동시에 공격하는 것도 적을 죽이면 좌표에서 바로 지우지 않고 check만 해둔뒤 3명의 궁수가 공격이 끝나면 

그제서야 적을 지우는 것도 놓쳤습니다.