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

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

어디가 틀린지 찾느라 힘들었다...

 

1. 궁수의 위치는 nC3으로 배치해 놓은 다음 가장 많은 적을 처치하는 경우는 언제인지를 찾는다. 

 

2. 성의 위치(행) castle을 n으로 놓고 성이 점점 위로 올라가는 것처럼 1씩 줄인다. castle-=1

왼쪽부터 검사해서 길이가 최소이면 해당 위치를 저장해놓고 모든 행을 봤을 때 길이가 가장 작았던 곳을 enemy 배열에 추가한다. 

여러 궁수가 같은 적을 공격할 수 있기 때문에 enemy에 같은 위치가 들어갈 수 있다. 돌면서 이미 방문한 곳을 0으로 만들고 적의 수를 또 더하지 않는 것만 중복되지 않도록 처리해주면 된다.

 

3. 모든 적이 예외가 되면 최종 해치운 적의 수와 ans를 비교해서 최대값으로 갱신해준다.

 

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

public class Main {
	static int[][] map;
	static int n,m,d;
	static int ans=0;
	static ArrayList<Integer> arrow=new ArrayList<>();
	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];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		nCr(0,0);	
		System.out.println(ans);
	}
	// 궁수의 위치가 정해지면 공격을 한다 
	private static void attack() {
		int temp=0;
		int castle=n; //초기 성의 위치 
		int[][] map2=new int[n][m]; // 방문된 곳은 0으로 표시하기 위해 다른 배열 만듦
		for (int i = 0; i < n; i++) {
			System.arraycopy(map[i], 0, map2[i], 0, m);
		}

		while(castle>0) { // 모든 궁수가 예외가 될 때까지 
			ArrayList<Integer[]> enemy=new ArrayList<>(); //공격할 적이 들어가는 배열 
		for (int k = 0; k < arrow.size(); k++) { //모든 궁수는 가장 가까운 적을 찾는다
			int min=Integer.MAX_VALUE;
			int []pos=new int[2]; // 현재 궁수에서 가장 가까운 적의 위치 담는 배열
			for (int j = 0; j < m; j++) {
				for(int i=castle-1;i>=0;i--) {
					int diff=Math.abs(castle-i)+Math.abs(arrow.get(k)-j);//적과의 거리

					if(map2[i][j]==1 && diff<=d) { //공격할 수 있는 거리에 적이 있다면
						if(diff<min) { //새로운 적이 더 가까이 있다면 거리와 위치 갱신
							min=diff;
							pos[0]=i;
							pos[1]=j;
						}
						break;
					}
				}
			}
			if(min!=Integer.MAX_VALUE) { //만약 공격할 수 있는 적이 있다면 enemy에 추가
			enemy.add(new Integer[]{pos[0],pos[1]});
			}
		}	
			for (int i = 0; i < enemy.size(); i++) { //모든 궁수가 공격할 수 있는 enemy배열
				if(map2[enemy.get(i)[0]][enemy.get(i)[1]]!=0) { //중복되는 적은 0처리해준다.
					temp+=1;
					map2[enemy.get(i)[0]][enemy.get(i)[1]]=0;
				}
			}
			castle-=1; // 성이 위로 올라감. 적이 더 가까이 다가옴

		}

		if(temp>ans)ans=temp; //전체 적의 수 갱신
	}
	
	// 궁수를 놓을 수 있는 경우의 수
	private static void nCr(int cnt,int start) {
		if(cnt==3) {
			attack();
			return;
		}
		for (int i = start; i < m; i++) {
			arrow.add(i);
			nCr(cnt+1,i+1);
			arrow.remove(arrow.size()-1);
		}
	}
	
}