BOJ 17135번: 캐슬 디펜스

문제

문제 바로가기> BOJ 17135번: 캐슬 디펜스

17135번: 캐슬 디펜스

 

풀이

 

1. 조합을 구현하여 궁수의 위치를 선정한다.  (`solution() 함수`)

 

2. 정해진 궁수의 위치를 기반으로, 다음을 과정을 반복한다.

 

궁수의 적 공격

- 공격할 적의 우선순위를 구하기 위해 , pq에서 사용할 ATTACK 구조체 내에서 bool operator를 재정의해주었다.

- 모든 궁수는 동시에 공격하므로, 공격 위치를 vector에 넣어두었다가 한 번에 공격해주었다.

   (이때, 이미 제거한 적을 또 count 해주어서는 안 된다.)

 

적의 이동

- 적이 이동하는 것보다, 궁수가 이동한다고 생각하는 것이 구현하기 더 쉽다.

  따라서 `ar-move`로 궁수의 행위치를 지정해주었다.

- 이때, 이미 지난 적들은 계산하지 않기 위해서, 궁수가 적을 공격할 때, `ar<=er `인 경우는 `continue` 해준다.

 

위 과정을 반복하면서 ans를 max 값으로 업데이트 해주면 된다.

 

C++

#include<iostream>
#include<vector>
#include<queue>
#define MAX 16
#define ENEMY 1
#define EMPTY 0
using namespace std;

struct POS { int r, c; };
vector<POS> archer, enemy;

struct ATTACK {
	int dist, r, c;
	bool operator < (const ATTACK &a) const {
		if (dist == a.dist) {
			if (c == a.c) return r < a.r;
			return c > a.c;
		} return dist > a.dist;
	}
};

int ans = 0;
int N, M, D;
int map[MAX][MAX];
int copy_map[MAX][MAX];

void input() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] == ENEMY) enemy.push_back({ i, j }); // 적의 위치 저장
		}
	}
}

int get_dist(int r1, int c1, int r2, int c2) {
	return abs(r1 - r2) + abs(c1 - c2);
}

int attack_enemy(int move) {

	int kill = 0;
	int ar, ac; // 궁수의 위치
	vector<POS> attack_pos; // 공격할 적들의 위치 

	for (int a = 0; a < (int)archer.size(); a++) { // 궁수 
		ar = archer[a].r-move;
		ac = archer[a].c;

		int er, ec, dist; // 적의 위치
		priority_queue<ATTACK> pq; // dist, row, col 
		for (int e = 0; e < (int)enemy.size(); e++) { // 적
			er = enemy[e].r;
			ec = enemy[e].c;
			dist = get_dist(ar, ac, er, ec); // 거리 계산
			if (dist > D || ar<=er || map[er][ec]==EMPTY) continue; // 공격 거리 D를 초과하는 경우, 격자판을 벗어난 적인 경우, 이미 공격한 적인 경우
			pq.push({dist, er, ec}); // maxHeap to minHeap
		}
		if (pq.size() == 0) continue;
		int r = pq.top().r;
		int c = pq.top().c;
		attack_pos.push_back({ r,c });
	}

	for (int i = 0; i < attack_pos.size(); i++) { // 모든 궁수는 동시에 공격
		int r = attack_pos[i].r;
		int c = attack_pos[i].c;
		if (map[r][c] == EMPTY) continue;
		map[r][c] = 0; // 선택된 적 공격 (같은 적이 여러 궁수에게 공격당할 수 있음)
		kill++;
	}
	return kill; // 제거한 적의 수
}

int simulation() {
	int kill = 0;
	for (int move = 0; move < N; move++) {
		kill += attack_enemy(move); // 적 공격 + 이동 (적 대신 궁수가 이동하는 것으로 대체)
	} return kill;
}

void solution(int cnt, int idx) {
	if (cnt == 3) { // 모든 궁수를 배치한 경우

		// 1. copy 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) copy_map[i][j] = map[i][j];
		}

		// 2. simulation
		ans = max(ans, simulation());

		// 3. recovery
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) map[i][j] = copy_map[i][j];
		}

		return;
	}
	for (int col = idx; col < M; col++) {
		archer.push_back({N, col}); //  궁수 배치
		solution(cnt + 1, col + 1); // 다음 궁수 배치
		archer.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution(0, 0);
	cout << ans;
}

 

Java

import java.io.*;
import java.util.*;

public class Main {
	
	static final int ENEMY = 1;
	static final int EMPTY = 0;
	
	static class Attack implements Comparable<Attack>{
		int dist, r, c;

		public Attack(int dist, int r, int c) {
			super();
			this.dist = dist;
			this.r = r;
			this.c = c;
		}

		@Override
		public int compareTo(Attack o) {
			if(this.dist == o.dist) return this.c - o.c; // 열이 더 작은 값
			return this.dist-o.dist; //  거리가 더 작은 값
		}
	}
	
	static int ans = 0;
	static int N, M, D;
	static int[][] map, copy_map;
	static List<int[]> archer = new ArrayList<int[]>();
	static List<int[]> enemy = new ArrayList<int[]>();

	public static void main(String[] args) throws Exception {
		
		// 1. input
//		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        copy_map = new int[N][M];
        
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0; j<M; j++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        		if(map[i][j] == ENEMY) enemy.add(new int[]{i, j}); // 적의 위치 저장
        	}
        }
        
        // 2. solution
        solution(0, 0);
        System.out.println(ans);
        br.close();
	}
	
	private static int attack_enemy(int move) {
		int kill = 0;
		int ar, ac; // 궁수의 위치
		List<int[]> attack_pos = new ArrayList<int[]>();; // 공격할 적들의 위치 

		for (int a = 0; a < (int)archer.size(); a++) { // 궁수 
			ar = archer.get(a)[0]-move;
			ac = archer.get(a)[1];
					
			int er, ec, dist; // 적의 위치
			PriorityQueue<Attack> pq = new PriorityQueue<>(); // dist, row, col 
			for (int e = 0; e < (int)enemy.size(); e++) { // 적
				er = enemy.get(e)[0];
				ec = enemy.get(e)[1];
				dist = Math.abs(ar - er) + Math.abs(ac - ec); // 거리 계산
				if (dist > D || ar<=er || map[er][ec]==EMPTY) continue; // 공격 거리 D를 초과하는 경우, 격자판을 벗어난 적인 경우, 이미 공격한 적인 경우
				pq.add(new Attack(dist, er, ec)); 
			}
			if (pq.isEmpty()) continue;
			int r = pq.peek().r;
			int c = pq.peek().c;
			attack_pos.add(new int[] { r,c });
		}

		for (int i = 0; i < attack_pos.size(); i++) { // 모든 궁수는 동시에 공격
			int r = attack_pos.get(i)[0];
			int c = attack_pos.get(i)[1];
			if (map[r][c] == EMPTY) continue;
			map[r][c] = 0; // 선택된 적 공격 (같은 적이 여러 궁수에게 공격당할 수 있음)
			kill++;
		}
		return kill; // 제거한 적의 수
	}
	
	private static int simulation() {
		int kill = 0;
		for (int move = 0; move < N; move++) {
			kill += attack_enemy(move); // 적 공격 + 이동 (적 대신 궁수가 이동하는 것으로 대체)
		} return kill;
	}
	
	private static void solution(int cnt, int idx) {
		if (cnt == 3) { // 모든 궁수를 배치한 경우

			// 1. copy 
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) copy_map[i][j] = map[i][j];
			}

			// 2. simulation
			ans = Math.max(ans, simulation());

			// 3. recovery
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) map[i][j] = copy_map[i][j];
			}

			return;
		}
		for (int col = idx; col < M; col++) {
			archer.add(new int[]{N, col}); //  궁수 배치
			solution(cnt + 1, col + 1); // 다음 궁수 배치
			archer.remove(archer.size()-1);
		}
	}

}