[BOJ] 17135. 캐슬 디펜스

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

17135번: 캐슬 디펜스

궁수 3명의 위치를 고르기 위해 완전 탐색을 하고 공격할 적을 찾기 위해서 BFS를 사용하였다.

문제에서 주어지는 사정거리를 계산하는 식이 딱 BFS 모양이기 때문이다.

적당히 잘 계산해주면 BFS를 사용하지 않아도 되긴 한다(처음에 이렇게 풀었었다)

 

 

먼저 배열은 궁수의 위치 때문에 행의 크기를 하나 더 크게 해주어야 한다.

n과 m의 범위가 최대 15이므로 배열의 범위는 16x15로 해주면 된다.

배열을 입력받았다면 n행의 궁수의 위치(y좌표)를 고르는 경우를 모두 구해준다.

0부터 m까지의 y좌표에서 해당 위치를 선택하는 경우와 안 하는 경우를 모두 구해주고,

3명의 위치를 모두 골라줬다면 공격을 시작한다.

 

 

공격을 시작할 때 주의할 점은 배열을 새로 만들어서 공격을 시작해야 한다.

궁수의 위치를 다시 골라줬을 때 처음 상태에서 다시 시작해야 하기 때문이다.

그러고 나서는 적이 모두 사라질 때까지 세명의 궁수의 공격과 적군의 이동을 반복하고

적군이 모두 사라졌을 때까지의 점수를 최댓값과 비교하여 저장한다.

 

 

공격할 적을 찾기 위해 bfs탐색을 하는데 각 궁수의 위치에서부터 시작해준다.

이전의 아기 상어 문제와 비슷하게 큐 사이즈를 저장해놨다가 큐 사이즈만큼을 먼저 진행하면

단계별로 bfs를 진행해줄 수 있다.

즉, 사정거리가 1 씩 증가할 때마다 적군을 찾았는지 확인하고 d(문제에서 주어진 사정거리) 보다 작은지 확인할 수 있다.

 해당 궁수의 bfs탐색에서 적군을 공격했거나, 사정거리를 넘어갈 때까지 적군을 찾지 못한 경우에는

탐색을 중단하고 다음 궁수의 bfs탐색을 진행한다.

 

 

적군을 찾은 경우에는 배열에 따로 죽은 적군의 좌표를 저장해두었다. 궁수들이 같은 적을 죽일 수도 있기 때문에

점수를 바로바로 계산해줄 수 없기 때문이다. 

3명의 궁수에 대한 적군 탐색이 끝났다면 위에서 저장해둔 죽은 적군들의 좌표를 검사해서 점수를 계산한 후 리턴한다.

한 번의 공격 턴이 끝났다면 적군들을 한 칸씩 아래로 내려주면 된다.

 

 

더 자세한 설명은 코드 참고!

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m, d;
int ans;
int firstmap[16][15];
int map[16][15];
 
int dx[] = { -1,0,0 };
int dy[] = { 0,-1,1 };
 
//궁수의 y좌표를 저장
vector<int> archer;
//궁수가 공격할 적을 탐색할 때 방문 체크할 배열
bool check[16][15];
//죽은 적을 체크
bool isdead[15][15];
 
 
//처음에 입력받은 배열을 복사
void mapcopy() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = firstmap[i][j];
        }
    }
}
 
 
//적이 모두 죽었는지 검사
bool isover() {
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 1) return false;
        }
    }
 
    return true;
}
 
 
//적군의 이동
void move() {
    //맨 밑칸부터 바로 윗칸의 적들을 내려준다.
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < m; j++) {
            map[i][j] = map[i - 1][j];
        }
    }
 
    //맨 윗줄은 모두 0으로 넣어준다
    for (int j = 0; j < m; j++) {
        map[0][j] = 0;
    }
}
 
 
//점수 계산
int calc() {
    int point = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //죽은 애들이 있을 때 point 증가
            if (isdead[i][j]) {
                point++;
                
                //죽은 곳 0으로 바꿔줌
                map[i][j] = 0;
            }
 
            //궁수는 3명이므로 한번의 턴에서 얻을 수 있는 최대 점수는 3점이므로 3점이 되면 바로 return
            if (point == 3) return point;
        }
    }
 
    //점수를 리턴
    return point;
}
 
 
//공격
int bfs() {
    //새로 궁수를 배치한 경우가 시작되므로 죽은 애들 체크하는 배열을 reset
    memset(isdead, false, sizeof(isdead));
    int point = 0;
 
    
    //궁수 3명에 대해서 각각 bfs탐색을 해준다.
    for (int i = 0; i < 3; i++) {
        queue<pair<int, int>> q;
        memset(check, false, sizeof(check));
 
        int y = archer[i];
        q.push(make_pair(n, y));
        check[n][y] = true;
 
        int qsize;
        int killx = 100;
        int killy = 100;
 
        int dist = 0;
        while (!q.empty()) {
            dist++;
 
            //현재 거리가 사정거리를 넘어가면 break
            if (dist > d) break;
            qsize = q.size();
 
 
            //사정거리까지의 단계별 진행을 위해서 큐사이즈만큼 진행한다.
            while (qsize-- > 0) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
 
                //위,왼,오 방향으로 이동(아래로는 갈 필요 없다)
                for (int k = 0; k < 3; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
 
                    //범위 체크
                    if (nx < 0 || ny < 0 || ny >= m) continue;
                    //방문 체크
                    if (check[nx][ny]) continue;
                    
                    
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
 
 
                    //적군이 있다
                    if (map[nx][ny] == 1) {
                        //더 왼쪽에 있는 애를 죽일거다
                        if (ny < killy) {
                            killx = nx;
                            killy = ny;
                        }
                    }
                }
 
 
            }
 
            //이번 턴에서 적군을 발견했다.
            if (killx != 100) {
                //죽이는 걸로 체크
                isdead[killx][killy] = true;
                
                //i번째 궁수는 죽일 적을 찾았으므로 탐색을 중단한다.
                break;
            }
        }
    }
 
 
    //이번 턴에서 얻은 점수를 계산
    point = calc();
 
 
 
    return point;
}
 
void select(int index, int cnt) {
    //궁수의 위치를 모두 정했다.
    if (cnt == 3) {
        int point = 0;
 
        //이번에 정한 궁수의 위치에서 공격할 배열을 새로 만들어준다.
        mapcopy();
 
        //모든 적이 죽을 때까지 반복
        while (!isover()) {
            //이번 시간의 공격에서의 점수
            point += bfs();
 
            //이동
            move();
        }
 
        //점수를 최댓값과 비교
        if (ans < point) ans = point;
 
        return;
    }
    if (index >= m) return;
 
 
    //index번째 열에 궁수를 배치
    archer.push_back(index);
    select(index + 1, cnt + 1);
 
 
    //index번째 열에 궁수를 배치하지 않는다.
    archer.pop_back();
    select(index + 1, cnt);
 
}
 
 
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 >> firstmap[i][j];
        }
    }
 
    select(0, 0);
 
    cout << ans << '\n';
 
    return 0;
}