[백준] 17135 캐슬디펜스

문제보기

삼성 역량테스트 A형 신청에 성공했스빈다!
약 2주정도 남았기 때문에… 당분간 코테 공부는 A형 기출 위주로 해볼 생각입니다.

캐슬디펜스 문제는 특별히 유의할 점은 없고, 그냥 문제 그대로 구현해주시면 됩니다. 저는 맵 전체를 가져오는것보다 적들의 위치를 리스트로 받아서 처리해줬습니다. 자세한 내용은 주석에~!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


// 적의 위치 및 생사여부를 나타낼 클래스 
class Pair{

	int x;
	int y;
	boolean alive;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
		alive = true;
	}
}

class Main{
	
	static int ip(String s) { return Integer.parseInt(s); };
	
	static int n;
	static int m;
	static int d;
	static List<Pair> anamies;
	
	// 적들이 한칸 전진합니다.
	static void nextTime() {
		for(Pair anamy : anamies) {
			if(anamy.x == n-1) { // 마지막행에 있던 적들은 성에 닿으면 없어집니다 
				anamy.alive = false;
			}else { // 그 외의 행에 있다면 행을 +1 해줍니다 
				anamy.x = anamy.x+1;
			}
		}
	}
	
	// 궁수의 위치를 바꿔줄 다음수열 구하기 메서드
	 public static boolean next_perm(int[] arr){
	        int i = arr.length -1; 
	        while( i > 0 && arr[i-1] <= arr[i]){
	            i--;
	        }
	        if(i <= 0){
	            return false; 
	        }
	        int j = arr.length -1; 
	        while( arr[j] >= arr[i-1] ){
	            j--;
	        }
	        
	        int temp = arr[j];
	        arr[j] = arr[i-1];
	        arr[i-1] = temp;
	        
	        int k = arr.length -1;
	        while( i < k ){
	            temp = arr[k];
	            arr[k] = arr[i];
	            arr[i] = temp;
	            i++;
	            k--;
	        }
	        return true; 
	  }


	// 궁수의 위치에 따른 가장 가까운 적의 인덱스를 반환하는 메서드
	 static int getClosestAnamy(int archer) {

		 int min = Integer.MAX_VALUE; // 적과의 최소 거리 
		 Pair closest = null; // 가장 가까운 적을 저장 
		 
		 for(Pair anamy : anamies) {
			 if(anamy.alive == false) continue; // 이미 죽은 적은 계산하지 않습니다 
			 
			 int dist = n - anamy.x + Math.abs(archer - anamy.y); // 거리공식에 따라 적과의 거리를 구합니다
			 
			 if(dist > d) continue; // 최대 조준가능 거리보다 초과되었다면 계산하지 않습니다 
			 if(dist < min) { // 최소거리 갱신
				 min = dist;
				 closest = anamy;
			 }else if( dist == min && anamy.y < closest.y) { // 만약 최소거리가 같다면 더 왼쪽에 있는 적을 택합니다
				 closest = anamy;
			 }
		 }
		 if(closest == null) { // 가장 가까운 적을 찾지 못했을 때 
			 return -1;
		 }

		 return anamies.indexOf(closest); // 가장 가까운 적의 인덱스를 반환합니다 
	 }
	 
	
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	n = ip(st.nextToken());
    	m = ip(st.nextToken());
    	d = ip(st.nextToken());
    	anamies = new ArrayList<Pair>();
    	
		// 맵을 살피며 적을 저장합니다 
    	for(int i = 0 ; i < n ; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j = 0 ; j < m ; j++) {
    			if(ip(st.nextToken()) == 1) {
    				anamies.add(new Pair(i, j));
    			}
    		}
    	}
		// 궁수의 위치를 나타낼 배열 
    	int[] archers = new int[m];
    	archers[0] = archers[1] = archers[2] = 1; // 초기에는 세명의 궁수가 모두 0,1,2 열에 위치하도록 해줬습니다
    	
    	int maxKill = 0; // 최대 사살 가능 적의 수 
    	
		// 궁수의 위치에 따라 매번 계산해줄 예정이므로 적의 정보는 미리 백업해 둡니다.
    	List<Pair> backup = new ArrayList<Pair>(); 
    	for(Pair anamy : anamies) {
    		backup.add(new Pair(anamy.x, anamy.y));
    	}
    	
    	do {
    		// 죽인 적의 수를 저장 
    		int kill = 0;
    		
    		for(int i = 0 ; i < n ; i++) {
				// 죽일 예정인 적들의 인덱스를 저장
    			ArrayList<Integer> targets = new ArrayList<Integer>(); 
        		for(int a = 0 ; a < m ; a++) { // 궁수 위치를 getClosestAnamy 메서드에 인자로 넣습니다
        			if(archers[a] == 0) continue; 
        			int target = getClosestAnamy(a); // 가장 가까운 위치의 적의 인덱스를 알아냅니다 
        			if(target != -1) { // 찾았다면 
        				targets.add(target); // 타켓에 저장
        			}
        		}
				// 타겟에 저장된 적들을 살펴봅시다 
        		for(int target : targets) {
        			if(anamies.get(target).alive == true) kill++; // 살아있던 녀석이라면 kill수를 높여주고
        			anamies.get(target).alive = false; // 죽은것으로 처리
        		}
        		if(kill > maxKill) { // 최대 사살 가능 적의 수 갱신
        			maxKill = kill;
        		}

        		nextTime(); // 적들을 전진시킵니다 
    		}
    		
			// 모두 구했다면 anamies를 초기화해줘야 합니다(궁수 위치 바꾸고 또 구해볼것이기 때문)
    		anamies = new ArrayList<Pair>();
    		
    		for(Pair anamy : backup) {
    			anamies.add(new Pair(anamy.x, anamy.y));
    		}
    		
    	}while(next_perm(archers));
    	
    	System.out.println(maxKill);
     }
}