[백준] 17135. 캐슬 디펜스

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

17135번: 캐슬 디펜스

---

문제에서 나온 순서대로 진행하면 되는 시뮬레이션 문제입니다. 문제를 풀면서 주의할 점이 2가지 있습니다.

(1) 궁수 3명을 배치할 수 있는 모든 자리에 배치하여 그 때 마다 게임을 진행 해 보면서 제거할 수 있는 적의 최대 수를 계산하는 것

(2) 궁수가 공격하는 적은 거리가 D 이하인 적 중에서 가장 가까운 적인데, 그러한 적이 여럿일 경우에 가장 왼쪽에 있는 적을 공격하며, 같은 적이 여러 궁수에게 공격당할 수 있다는 것 입니다.

궁수 3명이 한번 공격할 때 마다 한명의 적을 제거하는 것이 아니라 같은 궁수가 한명의 적을 동시에 공격할 수 있는 것이기 때문에 궁수가 한번 공격할때 마다 그 적을 제거하면 안됐습니다. 그래서 class 생성자로 die 라는 변수를 추가하여 몇번 공격당했나를 표시하는 방법으로 이 점을 해결했습니다.

그리고 주어진 2차원 배열을 처음에 입력받을 때만 이용하고, 궁수의 좌표와 적의 좌표만 따로 저장해서 계산할 때마다 초기값으로 초기화하는 방식을 이용하여 푼 것이 특징입니다.

[ 문제 풀이 ]

1. 처음에 입력받을 때, defaults 라는 ArrayList에 적군들의 위치를 저장했습니다. 이유는 3명의 궁수가 임의로 배치될 때 마다 copy() 라는 함수로 defaults 에 있는 적군의 위치들을 enemys 라는 ArrayList 에 복사하여 그 때마다 계산하기 위함입니다.

2. archers 라는 ArrayList 에는 recur() 함수의 재귀를 통해 뽑힌 3명의 궁수의 위치를 저장하였습니다.

3. 궁수 3명이 임의로 자리를 잡은 archers와 enemys 가 준비되면, 문제에서 시킨대로 하나씩 수행합니다.

① 한명의 궁수가 공격하는데 enemys의 모든 적의 좌표를 검사하면서 minLen 에는 공격하려는 궁수와 가장 거리가 가까운 길이를 계산하고, idx 에는 적의 인덱스를 저장합니다. 만약에 minLen과 거리가 같은 궁수가 있다면 가장 왼쪽 적을 죽이기 위해서 적의 y값을 비교하여 더 적은 y값을 가진 적의 인덱스를 idx에 저장합니다.

② 그러면 모든 적을 확인했을 때 죽여야할 적의 인덱스가 idx에 저장되어 있으므로 die 값을 + 1 해줍니다. 왜냐하면 다음 궁수가 똑같은 적을 죽일 수도 있기 때문입니다.

③ 이제 모든 궁수가 죽일 적을 표시했으면, enemys 를 다시 모두 확인하면서 die 값을 보고 그 값이 0 이 아니면 궁수가 죽이려고 표시한 것이기 때문에 그 적을 ArrayList에서 제거해줍니다.

④ 병사들의 좌표값을 아래로 한칸씩 움직이고 문제에서 모든 적이 격자판에서 제외되면 게임이 끝난다고 했으므로 위의 과정을 enemys 가 빌 때 까지 수행합니다.

4. 마지막에 잡은 병사의 수를 비교하면서 최대값을 구할 변수 MAX에 저장하고 출력하면 정답입니다.

---

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	// 궁수 archer
	// 적 enemy
	
	static int N, M, D, result, MAX = Integer.MIN_VALUE;
	static int[][] map;
	static ArrayList<Pair> enemys, archers, list, defaults;
	static boolean[] mask;
	static int[] temp;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		D = sc.nextInt();
		map = new int[N][M];
		
		defaults = new ArrayList();
		archers = new ArrayList();
		mask = new boolean[M+1];
		temp = new int[M+1];
		
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = sc.nextInt();
				// 적군들의 좌표와 생존여부 저장
				if(map[i][j] == 1) defaults.add(new Pair(i, j, 0));
			}
		}
		
		for(int i=0; i<3; i++) archers.add(new Pair(0, 0, 0));
		
		// (N, 0) ~ (N, M-1) 까지의 좌표들 중에서 궁수 3명을 임의로 뽑기
		temp[0]=1;
		recur(1, 0);
		System.out.println(MAX);
	}
	
	public static void recur(int start, int depth) {
		if(depth == 3) {
			result = 0;
			
			enemys = new ArrayList();
			copy();
			
			// archers에 궁수 3명을 뽑음
			for(int i=1; i<=3; i++) archers.set(i-1, new Pair(N, temp[i]-1, 0));
		
//			System.out.print("현재 병사의 위치  : ");
//			for(int i=1; i<=3; i++) {
//				Pair p = archers.get(i-1);
//				System.out.print(p.x + " " + p.y + " / ");
//			}
//			System.out.println();

			while(true) {
			
				// 1. 공격하기
				// 거리가 D 이하인 적 중에서 가장 가까운 적,
				// 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
				for(int i=0; i<archers.size(); i++) {
					Pair archer = archers.get(i);
					int minLen = Integer.MAX_VALUE;
					int idx = -1; // 죽여야할 적의 인덱스를 저장하는 변수
					
					for(int j=0; j<enemys.size(); j++) {
						Pair enemy = enemys.get(j);
						// 거리가 D 이상이면 컨티뉴
						if(getLen(archer, enemy) > D) continue;
						else { // 거리가 D 이하이면
							
							// 거리를 비교해서 최소값과 그 적의 인덱스를 비교
							if(getLen(archer, enemy) < minLen) {
								minLen = getLen(archer, enemy);
								idx = j;
								continue;
							}							
							
							// 거리가 같다면 가장 왼쪽 적을 죽이기 위해서 왼쪽인덱스 비교저장
							if(getLen(archer, enemy) == minLen) {
								if(enemys.get(idx).y > enemys.get(j).y) {
									idx = j;
								}
							}
							
						}
					}
					// minLen 값이 그대로이면 죽일 적이 없다는 뜻이므로 컨티뉴
					if(minLen == Integer.MAX_VALUE) continue;
					if(idx == -1) continue;
					Pair p = enemys.get(idx);
					enemys.set(idx, new Pair(p.x, p.y, p.die+1));
				}
				
				for(int i=0; i<enemys.size(); i++) {
					Pair p = enemys.get(i);
					if(p.die > 0) {
						enemys.remove(i);
						i--;
//						System.out.print("죽은 병사의 좌표 : " + p.x + " " + p.y + " / ");
						result++; 
					}
				}
//				System.out.println();
				
				// 병사들 아래로 한칸씩 움직이기
				for(int i=0; i<enemys.size(); i++) {
					Pair p = enemys.get(i);
					p.x += 1;
					if(p.x >= N) {
						enemys.remove(i);
						i--;
					} else enemys.set(i, new Pair(p.x, p.y, p.die));
				}
				
				if(enemys.isEmpty()) break;
			}
			
//			System.out.println("잡은 병사의 수 : " + result);
			MAX = Math.max(MAX, result);
			
//			System.out.println();
			return;		
		}
		for(int i=temp[start-1]; i<=M; i++) {
			if(mask[i]) continue;
			temp[start] = i;
			mask[i] = true;
			recur(start+1, depth+1);
			mask[i] = false;
		}
	}
	
	public static int getLen(Pair p1, Pair p2) {
		return Math.abs(p1.x-p2.x) + Math.abs(p1.y-p2.y);
	}
	
	public static void copy() {
		for(int i=0; i<defaults.size(); i++) {
			Pair p = defaults.get(i);
			enemys.add(new Pair(p.x, p.y, 0));
		}
	}
}

class Pair {
	int x;
	int y;
	int die;
	
	Pair(int x, int y, int die){
		this.x=x;
		this.y=y;
		this.die = die;
	}
}