[BOJ] 17135번 : 캐슬 디펜스(C++)

문제 링크 : 백준 17135번

[문제 접근]

구현문제로 BFS를 이용해서 접근했다.

1. 순열을 이용해 궁수를 배치한다.(next_permutation)
2. temp배열에 원래 arr배열을 복사한다.
3. search함수로 들어가서 적이 남아있는지 검사한다. 적이 남아있다면 4번으로 가고 남아있지 않다면 7번으로간다.
4. BFS함수로 들어가 적을 제거한다.
   • 왼쪽, 위쪽, 오른쪽 순으로 탐색하면서 우선순위를 만족시켜준다.
   • 적을 제거하면 바로 다음 궁수로 넘어간다.
   • 제거한 적이 중복되지 않게 주의한다.
5. next함수로 들어가서 적들을 이동시켜준다.
6. 다시 3번으로 간다.
7. 최대값을 비교해 ans를 갱신시켜준다.
8. 순열을 끝까지 돌지 않았다면 1번으로 가고 다 돌았다면 9번으로 간다.
9. ans를 출력하면 정답

---

m개를 기준으로 3개씩 궁수를 배치해야되는데 5개를 기준으로 3개씩 배치하게 짜놔서 어처구니없게 2시간 동안 삽질했다...

[소스 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int n,m,d;
int arr[16][16];
int temp[16][16];
bool visit[16][16];
int dx[3] = {0,-1,0};
int dy[3] = {-1,0,1};
vector<int> seq;

struct node {
    int x, y, num;
};

int BFS() {
    int cnt=0;
    queue<pair<int ,int> > tmp;
    for(int i=0 ; i<m ; i++) {
        if(seq[i] == 1) {
            if(temp[n-1][i] == 1) {
                tmp.push(make_pair(n-1, i));
                continue;
            }
            memset(visit, false, sizeof(visit));
            queue<node> q;
            node p = {n-1, i, 1};
            q.push(p);
            visit[n-1][i] = true;

            while(!q.empty()) {
                int x = q.front().x;
                int y = q.front().y;
                int num = q.front().num;
                q.pop();
                if(num>d) continue;

                if(temp[x][y] == 1) {
                    tmp.push(make_pair(x, y));
                    break;
                }

                for(int j=0 ; j<3 ; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    if(x<0 || x>=n || y<0 || y>=m) continue;
                    if(!visit[nx][ny]) {
                        node np = {nx, ny, num+1};
                        q.push(np);
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }

    while(!tmp.empty()) {
        int x = tmp.front().first;
        int y = tmp.front().second;
        tmp.pop();
        if(temp[x][y] == 1) {
            cnt++;
            temp[x][y] = 0;
        }
    }

    return cnt;
}

bool search() {
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            if(temp[i][j] == 1) return true;
        }
    }

    return false;
}

void next() {
    for(int i= m-1 ; i>=0 ; i--) {
        for(int j=n-1 ; j>=0 ; j--) {
            if(j==n-1) {
                temp[j][i] = 0;
            } else {
                if(temp[j][i] == 1) {
                    temp[j][i] = 0;
                    temp[j+1][i] = 1;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> d;
    for(int i=0 ; i<n ; i++) {
        for(int j=0 ; j<m ; j++) {
            cin >> arr[i][j];
        }
    }
    for(int i=0 ; i<m-3 ; i++) {
        seq.push_back(0);
    }
    for(int i=0 ; i<3 ; i++) {
        seq.push_back(1);
    }
    
    int ans=0;
    do{
        for(int i=0 ; i<n ; i++) { // arr배열은 망가지면 안되므로 temp배열에 복사해서 탐색
            for(int j=0 ; j<m ; j++) {
                temp[i][j] = arr[i][j];
            }
        }

        int num=0;
        while(search()) { // 1이 남아있다면
            num += BFS(); // 탐색하면서 적을 제거하고
            next(); // 적이 이동한다.
        }
        if(ans<num) {
            ans = num;
        }
    }while(next_permutation(seq.begin(), seq.end()));

    cout << ans;

    return 0;
}```