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

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

17135번: 캐슬 디펜스

 

 

삼성 A형문제임 그냥 구현 구현 구현 문제

조합으로 매번 궁수의 자리를 바꿔주었고

그때마다 BFS를 통해서 좌, 위 우 순으로 이동

왜냐하면 좌 부터 가야지 문제 조건인 같은 거리면 왼쪽부터 공격합니다를 구현할 수 있으니까

뒤는 갈 필요없음 

 

그리고 죽인 적들의 수 중에 최댓값 출력

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
 
int arr[17][17];
int n, m, d;
 
//왼 위 오른
int dx[3] = {0,-1,0 };
int dy[3] = {-1,0,1  };
 
bool visit[17][17];
bool check[16];
 
int answer = 0;
int num;
 
 
void bfs() {    
    //현재 궁수가 있는 행 좌표, 항상 제일 밑에서 시작
    int pos = n;
 
    //죽은 위치 체크용
    bool kill[17][17];
 
    //배열 복사본
    int arr_copy[17][17];
 
    //일단 배열 복사                
    for (int a = 0; a < n; a++)
        for (int b = 0; b < m; b++)
            arr_copy[a][b] = arr[a][b];
 
    memset(kill, false, sizeof(kill));
 
    while (pos > 0) {
        for (int i = 0; i < m; i++) {
            //궁수가 있는 자리에서 시작
            if (check[i] == true) {                    
 
                //매 경우 visit 초기화
                memset(visit, false, sizeof(visit));
            
                visit[pos][i] = true;
                queue<pair<int, int>> q;
                q.push({ pos,i });
 
                while (!q.empty()) {
                    int a = q.front().first;
                    int b = q.front().second;
                    q.pop();
 
                    for (int j = 0; j < 3; j++) {
 
                        int da = a + dx[j];
                        int db = b + dy[j];
 
                        if (da >= 0 && db >= 0 && da < pos && db < m)
                            //방문한적없고, 사정거리 안에 있을때
                            if (visit[da][db] == false && (abs(da-pos)+abs(db-i))<=d) {                                                            
 
                                //적이 있을경우
                                if (arr_copy[da][db] == 1) {
                                    //큐 비워주고 킬마크
                                    while (!q.empty())
                                        q.pop();
                                    kill[da][db] = true;
                                    break;;
                                }
                                q.push({ da,db });
                                visit[da][db] = true;
                            }
                    }
                }
            }            
        } // 모든 궁수에 대한 한차례의 공격이 끝난 후
        //돌면서 공격당한 녀석이 있는 배열 0으로 만들어주고
        for(int a = 0 ; a<n ; a++)
            for (int b = 0; b < m; b++) {
                if (kill[a][b] == true) arr_copy[a][b] = 0;
            }
        //궁수 한 칸 위로 전진
        pos--;
    }
    //모든 공격이 끝난 후 죽은 적 갯수 셈
    for (int a = 0; a < n; a++)
        for (int b = 0; b < m; b++)
            if (kill[a][b] == true) num++;
 
    answer = max(answer, num);    
}
 
//궁수의 위치를 정하는 조합 사용
void dfs(int idx, int cnt) {
 
    //궁수가 3명일때 cnt 기준 1 2 3 순서를 전부 정했을때 공격 시작
    if (cnt == 3) {
        num = 0;
        bfs();
 
        return;
    }
 
    for (int i = idx; i < m; i++) {
        if (check[i] == true) continue;
        check[i] = true;
 
        dfs(i, cnt + 1);
        check[i] = false;
    }
}
 
int main() {
    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 << answer;
 
    return 0;
}