캐슬 디펜스(백준 17135번, 자바)☆☆☆☆

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

17135번: 캐슬 디펜스

 

 

 

1. dfs를 이용하여 3명의 궁수를 배치하는 경우의 수를 구하자

2. 적의 좌표는 enemy2 리스트에 저장하고, 궁수 배치할 때마다 enemy1리스트에 복사해서, 적의 좌푤를 관리한다.

3. 적이 죽은 경우나, 제외되는 경우는 enemy1리스트에서 적을 제거한다.

4. 적이 아래로 한 칸 이동하는 것은 궁수의 x좌표를 위로 한칸씩 올리는 방식으로 구현한다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N,M,D;
	static int[][] map;
	static ArrayList<int[]> enemy2, enemy1;//원본 적의 좌표 리스트, 복사본
	static boolean[] visit; // 궁수의 위치
	static boolean[] visit2;//적의 제거 여부 
	static int answer=Integer.MIN_VALUE;
	
	static int archerX;//궁수의 x좌표 
	
	public static void main(String[] args) throws IOException {
		
		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];
		enemy1=new ArrayList<>(); 
		enemy2=new ArrayList<>(); 
		visit=new boolean[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]==1) enemy2.add(new int[] {i,j});
			}
		}
		
		archerX=N; //궁수의 x좌표
		putArcher(0,0); //궁수 배치 
		
		System.out.println(answer);
		
	}

	static void putArcher(int idx, int cnt) { 
		
		if(cnt==3) { //배치한 궁수가 3명이 되면 
			archerX=N;//궁수의 x좌표 setting
			enemy1=(ArrayList<int[]>) enemy2.clone(); //적 위치 리스트 복사 
			int killEnemyCnt=0; //kill한 적의 수 
			while(archerX>0) { //모든 적이 살아있을 때까지  = 궁수의 좌표가 1이상일 때까지
				killEnemyCnt+=kill(); //죽은 적의 개수를 더하고
				archerX--;//궁수의 좌표는 줄인다.
				UpdateEnemy(); //제외되거나 죽은 적, 리스트에서 제거 
				}
		
			answer=Math.max(answer,killEnemyCnt); //죽은 적의 최대값이 정답이 됨 
			return;
		}
		
		for(int i=idx;i<M;i++) {
			if(visit[i])continue;
			visit[i]=true;
			putArcher(i,cnt+1);
			visit[i]=false;
		}
	}
	
	
	
	static int kill() { //궁수들의 x좌표를 입력, 죽은 적의 수 리턴 
		
		int killCnt=0;
		visit2=new boolean[enemy1.size()];
		
		int minDistance;
		int killIndex=0;
		
		for(int i=0;i<M;i++) {
			minDistance=Integer.MAX_VALUE;
			killIndex=-1;
			
			if(visit[i]) {//궁수가 있다면
				for(int j=0;j<enemy1.size();j++) {
					int distance=Math.abs(enemy1.get(j)[0]-archerX)+Math.abs(enemy1.get(j)[1]-i);
					if((distance < minDistance) && distance<=D) {
						minDistance=distance;
						killIndex=j;
					}
					if((distance ==minDistance) && distance<=D ) {
						if(enemy1.get(killIndex)[1]>enemy1.get(j)[1]) killIndex=j;						
					}
				}
				if(killIndex==-1) continue;
				if(!visit2[killIndex]) {
					killCnt++;
					visit2[killIndex]=true;
				}
			}
		}
		return killCnt;
	}
	
	
	static void UpdateEnemy() { //제외되거나 죽은 적 제거하기 
		
		for(int j=enemy1.size()-1;j>=0;j--) {
			if(enemy1.get(j)[0]>=archerX || visit2[j]) {
				enemy1.remove(j);	
			}
		}
	}
	

}