[백준] 17135번 캐슬디펜스 (java)

문제

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

17135번: 캐슬 디펜스

---

풀이

아처 3명의 위치를 0~m-1사이에서 정해야 함 -> 조합-기저조건: cnt==3(아처 3명의 위치가 정해졌을때)

enemy의 경우, 변경되면 안되는 정보이므로 tmp_enemy를 local 변수로 만들어 기존 데이터 보호

tmp_enemy가 비어있을 때까지(적이 모두 없어질때까지) while문을 돌아, 적을 죽인 횟수를 구한다.

 

이때 적과의 거리가 유효값이라면 min값(거리 최솟값)을 바꿔주고 죽일 적의 위치를 변경해주는것이 일반적이지만,

이 문제에선 거리가 같다면 가장 왼쪽의 적을 공격해야하기 때문에 현재 j값이 기존에 죽일 적의 위치의 j값보다 클때는 무시.

 

또한, 같은 적을 공격할 수 있으므로 적을 바로 죽일 수는(리스트에서 삭제할 수는) 없으므로 모아두었다가 한번에 remove를 해줌.

공격이 끝나면 적의 위치를 조정해야 하므로 리스트를 뒤에서부터 순회하며 맵밖으로 나간 적 삭제, 맵 안의 적 이동 시킴.

 

while문을 나오게 되면, 이전의 조합들 중 최대 kill값과 현재 kill값을 비교하여 max_kill값 설정

 

---

코드

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

public class Main{
	static int n,m,d;
	static List<int[]> enemy;
	static int[] archer;
	static int max_kill;
	public static void main(String[] args) throws Exception {
		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());
		enemy = new ArrayList<int[]>();
		archer = new int[3];
		max_kill = 0;
		for(int i =0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < m ; j++) {
				if(Integer.parseInt(st.nextToken()) == 1) {
					enemy.add(new int[] {i,j});
				}
			}
		}
		attack(0,0);
		System.out.println(max_kill);
	}
	
	public static void attack(int cnt, int start) {
		if(cnt == 3) {		//기저조건: 아처 3명의 위치가 정해졌을 경우
			int tmp_max_kill = 0;
			List<int[]> tmp_enemy = new ArrayList<int[]>();															//enemy를 계속 변경시켜줘야하기 때문에, 기존의 enemy유지 해야함
			for(int i =0 ; i < enemy.size() ; i++) tmp_enemy.add(new int[] {enemy.get(i)[0], enemy.get(i)[1]});		//초기상태의 enemy복사
			while(!tmp_enemy.isEmpty()) {																			//맵에 적들이 없을때까지
				int[][] killed = new int[3][2];																		//궁수가 죽인 적 위치 저장하는 변수
				for(int i =0 ; i < 3 ; i++) {																		//궁수마다 죽일 적 선택
					int min = Integer.MAX_VALUE;		
					for(int j =0 ; j < tmp_enemy.size() ; j++) {													//적 위치마다 저장
						int dis = Math.abs(tmp_enemy.get(j)[0] - n) + Math.abs(tmp_enemy.get(j)[1] - archer[i]);	//적과의 거리 계산
						if(dis<=d && min >= dis ) {			//적과의 거리가 유효값일 때
							if(min == dis && killed[i][1] < tmp_enemy.get(j)[1] ) continue;							//위치가 같을 시, 가장 왼쪽에 있는 적을 kill
							min = dis;
							killed[i] = tmp_enemy.get(j);
						}
					}
				}
				for(int i =0 ; i < 3 ; i++) {						//같은 적을 죽일 수 있기 때문에, 한번에 처리해 주어야 함
					if(tmp_enemy.contains(killed[i])) {				//앞선 궁수가 이미 죽였을 수도 있기 때문에 현재 적이 있는지 체크
						tmp_enemy.remove(killed[i]);				//죽인 적을 리스트에서 삭제
						tmp_max_kill++;								//죽인 횟수 증가
					}
				}
				for(int i =tmp_enemy.size()-1 ; i >=0 ; i--) {		//리스트이기 때문에 뒤에서 부터 삭제
					if(tmp_enemy.get(i)[0] < n-1) 					//맵 밖으로 나가지 않을땐 아래로 한칸 이동
						tmp_enemy.get(i)[0] ++;
					else 
						tmp_enemy.remove(i);						//맵 밖으로 나가는경우 리스트에서 삭제
				}
			}
			max_kill = Math.max(max_kill, tmp_max_kill);			//지금까지 조합중, 가장 많이 죽였던 값 선택
			return;
		}
		for(int i = start; i < m ; i++) {
			archer[cnt] = i;		//아처의 위치
			attack(cnt+1, i+1);
		}
	}
}