[백준 17135번] 캐슬 디펜스

문제 링크: https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

<문제 풀이> 우선순위큐, 시뮬레이션 

 

저는 이 문제를 다음과 같은 순서로 구현했습니다.

 

1. 적들을 아래로 한 칸 이동시키기

N행을 모두 0으로 만듭니다. (성에 도달한 적은 게임에서 제외)
N-1행부터 1행까지 순회하면서 i행에 있는 모든 원소를 i + 1행으로 옮긴다.

 

void moveEnemy() {
	for (int c = 1; c <= m; c++) { // N행에 있는 적들은 게임에서 제외
		board[n][c] = 0;
	}
	for (int r = n - 1; r >= 1; r--) { // N-1행 ~ 1행에 있는 모든 적을
		int nr = r + 1;
		for (int c = 1; c <= m; c++) {
			board[nr][c] = board[r][c]; // 아래로 한 칸 이동한다.
			board[r][c] = 0;
		}
	}
}

2. 궁수 3명을 N + 1 행에 배치하는 조합을 DFS로 구현

기본적인 조합을 구하는 DFS로 N + 1행에 궁수들을 3명 배치하면 됩니다.
궁수가 3명이 배치되면, 그때 모든 적이 격자판에서 제외될 때까지 공격과 적 이동을 반복하면 됩니다.

궁수가 3명이 배치될 때마다 새로운 게임이 진행되므로 초기 입력받은 격자판으로 복원하는 부분도 필요합니다. 

 

void recovery() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			board[i][j] = temp[i][j];
		}
	}
}

//궁수 3명을 배치하는 조합 + 게임 진행
void dfs(int idx, int k) {
	if (k == 3) { // 궁수 3명 배치 완료
		recovery(); // 매 조합마다 새로운 게임을 진행하기 위해 격자판 복구
		int capturedEnemy = 0; //잡힌 적의 수
		while (getEnemyCnt()) { // 모든 적이 격자판에서 제외될 때까지 반복
		    capturedEnemy +=  attack(); // 공격
			moveEnemy(); // 적 이동
		}
		ans = max(ans, capturedEnemy);
	}
	for (int c = idx + 1; c <= m; c++) {
		board[n + 1][c] = 1;
		dfs(c, k + 1);
		board[n + 1][c] = 0;
	}
}

 

3. 격자판에 존재하는 모든 적 구하기.
이 부분은 2차원 배열을 순회하면서 적들의 수를 세어주고 그 수를 리턴하는 함수를 작성하면 됩니다.

 

//격자판의 적의 수 리턴
int getEnemyCnt() {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if(board[i][j]) cnt++;
		}
	}
	return cnt;
}

 

4. 궁수들의 적 공격 구현

 

모든 궁수는 동시에 공격을 합니다. 궁수가 공격하는 조건은 다음과 같습니다.

1) 궁수와의 거리가 D이하인 적 중에서 가장 가까운 적

2) 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적

위 조건을 만족하는 적의 좌표 값을 r, c라고 할 때 board[r][c]의 값을 0으로 만들면 적을 제거할 수 있습니다.

위 조건을 만족하는 적의 좌표 값을 O(lgN)에 알아내는 방법은 우선순위큐를 사용하는 것입니다.

 

다음과 같이 적의 위치와, 궁수와 떨어진 거리를 멤버변수로 가지고 있는 클래스를 작성한 뒤, 비교함수를 작성하면 됩니다.

class Enemy {
public:
	int x, y; // 적의 위치
	int dist; // 궁수와 떨어진 거리
	Enemy(int x, int y, int dist) {
		this->x = x;
		this->y = y;
		this->dist = dist;
	}
};

// 가장 가까운 적이고, 가장 왼쪽에 있는 적을 공격
struct cmp {
	bool operator()(const Enemy &a, const Enemy &b){
		if (a.dist == b.dist) return a.y > b.y;
		else return a.dist > b.dist;
	}
};

 

이제 우선순위큐 3개를 선언하고( 배열 -> pq[3]) 각각의 우선순위 큐에 1번 궁수, 2번 궁수, 3번 궁수의 공격 사정거리 안에 들어오는 적들을 큐에 삽입하면 됩니다.

 

적들은 우선순위 큐의 top()에 있습니다.

 

 

 

적들을 실제로 제거할 때는 궁수 3명의 우선순위큐에 적들을 삽입하는 과정이 끝나고 난 뒤에 제거해야 합니다.

모든 궁수는 동시에 공격할 수 있기 때문입니다.

또한 사정거리 안에 없는 적들도 있을 수 있기 때문에 우선순위큐가 비어있는지도 확인해야 합니다.

 

//궁수가 공격한 적의 수를 리턴
int attack() {
	priority_queue<Enemy, vector<Enemy>, cmp> pq[3]; //각 궁수가 공격할 수 있는 적을 원소로 가지고 있음
	vector<pair<int, int> > archers; //각 궁수의 위치
	for (int i = 1; i <= m; i++) {
		if (board[n + 1][i]) archers.push_back({ n + 1, i });
	}
	for (int k = 0; k < 3; k++) { //각각의 궁수에 대해서
		for (int r = 1; r <= n; r++) {
			for (int c = 1; c <= m; c++) {
				int dist = abs(r - archers[k].R) + abs(c - archers[k].C);
				if (board[r][c] && dist <= d) { //사정거리 안에 있는 적을
					pq[k].push({ r, c, dist}); //우선순위 큐에 삽입
				}
			}
		}
	}
	int cnt = 0;
	for (int k = 0; k < 3; k++) {//각각의 궁수에 대해서
		if (pq[k].empty()) continue;  //사정거리 안에 적이 없으면 무시
		auto enemy = pq[k].top();
		if (board[enemy.x][enemy.y]) { // 사정거리 안에 있는 적 중에서 가장 가까우며, 가장 왼쪽에 있는 적 하나를 공격
			board[enemy.x][enemy.y] = 0;
			cnt++;
		}
	}
	return  cnt;
}

 

 

<전체 C++소스코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
 
#define R first
#define C second
 
int n, m, d;
int board[17][17];
int temp[17][17];
int ans = 0;
 
class Enemy {
public:
    int x, y; // 적의 위치
    int dist; // 궁수와 떨어진 거리
    Enemy(int x, int y, int dist) {
        this->x = x;
        this->y = y;
        this->dist = dist;
    }
};
 
void recovery() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            board[i][j] = temp[i][j];
        }
    }
}
 
// 가장 가까운 적이고, 가장 왼쪽에 있는 적을 공격
struct cmp {
    bool operator()(const Enemy &a, const Enemy &b){
        if (a.dist == b.dist) return a.y > b.y;
        else return a.dist > b.dist;
    }
};
 
 
void moveEnemy() {
    for (int c = 1; c <= m; c++) { // N행에 있는 적들은 게임에서 제외
        board[n][c] = 0;
    }
    for (int r = n - 1; r >= 1; r--) { // N-1행 ~ 1행에 있는 모든 적을
        int nr = r + 1;
        for (int c = 1; c <= m; c++) {
            board[nr][c] = board[r][c]; // 아래로 한 칸 이동한다.
            board[r][c] = 0;
        }
    }
}
 
//궁수가 공격한 적의 수를 리턴
int attack() {
    priority_queue<Enemy, vector<Enemy>, cmp> pq[3]; //각 궁수가 공격할 수 있는 적을 원소로 가지고 있음
    vector<pair<int, int> > archers; //각 궁수의 위치
    for (int i = 1; i <= m; i++) {
        if (board[n + 1][i]) archers.push_back({ n + 1, i });
    }
    for (int k = 0; k < 3; k++) { //각각의 궁수에 대해서
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= m; c++) {
                int dist = abs(r - archers[k].R) + abs(c - archers[k].C);
                if (board[r][c] && dist <= d) { //사정거리 안에 있는 적을
                    pq[k].push({ r, c, dist}); //우선순위 큐에 삽입
                }
            }
        }
    }
    int cnt = 0;
    for (int k = 0; k < 3; k++) {//각각의 궁수에 대해서
        if (pq[k].empty()) continue;  //사정거리 안에 적이 없으면 무시
        auto enemy = pq[k].top();
        if (board[enemy.x][enemy.y]) { // 사정거리 안에 있는 적 중에서 가장 가까우며, 가장 왼쪽에 있는 적 하나를 공격
            board[enemy.x][enemy.y] = 0;
            cnt++;
        }
    }
    return  cnt;
}
 
 
//격자판의 적의 수 리턴
int getEnemyCnt() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if(board[i][j]) cnt++;
        }
    }
    return cnt;
}
 
//궁수 3명을 배치하는 조합 + 게임 진행
void dfs(int idx, int k) {
    if (k == 3) { // 궁수 3명 배치 완료
        recovery(); // 매 조합마다 새로운 게임을 진행하기 위해 격자판 복구
        int capturedEnemy = 0; //잡힌 적의 수
        while (getEnemyCnt()) { // 모든 적이 격자판에서 제외될 때까지 반복
            capturedEnemy +=  attack(); // 공격
            moveEnemy(); // 적 이동
        }
        ans = max(ans, capturedEnemy);
    }
    for (int c = idx + 1; c <= m; c++) {
        board[n + 1][c] = 1;
        dfs(c, k + 1);
        board[n + 1][c] = 0;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m >> d;
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= m; c++) {
            cin >> board[r][c];
            temp[r][c] = board[r][c];
        }
    }
    dfs(0, 0);
    cout << ans;
    return 0;
 
}