[BOJ][JAVA] 17135 - 캐슬 디펜스

문제 출처 : https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

 

문제

 

 

 

설명

꽤나 복잡한 시뮬레이션 문제였지만, 로직 자체는 크게 어렵지 않아서 조건에 따라 차근차근 코드를 짜 나가다 보면 해결할 수 있는 문제였습니다.

여기서 주의할 점은 각 케이스에 대해서 시뮬레이션을 돌릴 때, 원본이 변하면 안 되기에 복사본을 만든 후 그 복사본에서 시뮬레이션을 해야 한다는 것입니다.

한꺼번에 구현하려 하지 않고, 적절한 단위로 끊어서 함수로 구성해 나갔기 때문에 조금이나마 수월하게 문제를 풀 수 있었다고 생각합니다.

주석을 자세히 달아놨으니, 코드 이해에 도움이 되셨으면 좋겠습니다! 

 

 

 

코드

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

public class BOJ17135_CastleDefense {
	
	static class Enemy{ //적의 위치
		int x, y;

	public Enemy(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	   }
	}
	
	static int N, M, D;
	static ArrayList<Enemy> enemies;
	static int[] selected; //뽑은 궁수의 위치(y좌표) (x좌표는 N으로 일정)
	static int maxKill=Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); //행의 갯수
		M = sc.nextInt(); //열의 갯수
		D = sc.nextInt(); //제한 거리
		
		enemies = new ArrayList<>();
		selected = new int[3];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(sc.nextInt()==1) {
					enemies.add(new Enemy(i, j)); //적의 위치 저장
				}
			}
		} //입력 완료
		
		comb(0, 0);
		System.out.println(maxKill);
		
	}

	private static void comb(int cnt, int start) { //궁수의 위치를 M개 중 세 군데 뽑음
		
		if(cnt==3) { //다 뽑았다면
			
			//복사본 저장
			ArrayList<Enemy> copy = new ArrayList<>();
			for(Enemy e : enemies) {
				copy.add(new Enemy(e.x, e.y)); //아예 새로운 객체를 생성하는, 깊은 복사!
			}
			
			//복사본을 가지고 시뮬레이션 함 -> 하나의 조합에서 죽일 수 있는 적의 갯수를 구함
			int kill = startSimul(copy, selected);
			maxKill = Math.max(maxKill, kill);
			return;
		}
		
		for(int i=start; i<M; i++) {
			selected[cnt] = i;
			comb(cnt+1, i+1);
		}
		
	}

	private static int startSimul(ArrayList<Enemy> elist, int[] archers) { //죽일 수 있는 적의 갯수를 리턴
		int count=0;
		
		while(elist.size()!=0) { //적이 다 제거될 때까지 게임이 진행됨
			ArrayList<Enemy> temp = new ArrayList<>(); //죽일 적의 리스트
			for(int a : archers) { //각 궁수가 죽일 적을 temp에 담음
				int targetIndex = FindNearestOne(a, elist); //궁수와 가장 가까운 공격 가능한 적의 인덱스 구하기
				if(targetIndex>=0) { //죽일 수 있는 적이 있다면
					temp.add(elist.get(targetIndex));
				}
			}
			
			//적을 제거함(중복값 고려)
			for(Enemy e : temp) {
				if(elist.remove(e)) //e값이 있을 때에만 true리턴함
					count++;
			}
			goDown(elist); //적들이 한 칸씩 내려옴
		}
		return count;
	}

	private static void goDown(ArrayList<Enemy> elist) { //적들이 한 칸씩 내려옴 ( N행에 도착하면 게임에서 제외됨)
		
		for(int i=0; i<elist.size(); i++) {
			elist.get(i).x++;
			if(elist.get(i).x==N) {
				elist.remove(i);
				i--;
			}
		}
	}

	private static int FindNearestOne(int a, ArrayList<Enemy> elist) { //궁수의 위치로부터 가장 가까이 있는 적의 인덱스를 리턴
		//D 거리 안에 있어야 공격 가능하고, 가장 가까운 거리가 여럿이면 가장 왼쪽에 있는 적 공격가능함.
		int minDist = Integer.MAX_VALUE;
		int minCol=16;
		int minIdx=-1;
		
		for (int i = 0; i < elist.size(); i++) {
			
			Enemy e = elist.get(i);
			
			int dist = (N-e.x) + Math.abs(a - e.y);
			if(dist>D) { //이 적은 공격할 수 없음.
				continue;
			} else if (dist<minDist) {
				minDist=dist;
				minCol = e.y;
				minIdx = i;
			} else if(dist==minDist) {
				if(e.y < minCol) { //더 왼쪽이라면 업데이트
					minCol=e.y;
					minIdx=i;
				}
			}
		}
		return minIdx;
	}
}