[Java] BOJ 17135번 캐슬 디펜스

17135번: 캐슬 디펜스

---

풀이

문제에서 주어진 조건대로 처리하여 해결했습니다.

---

코드

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

public class Main {
	public static class Enemy {
		int i;
		int j;
		
		public Enemy(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}
	}
	public static int N, M, D;
	public static List<Enemy> enemyInfo;
	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());
		
		enemyInfo = new ArrayList<Enemy>();
		
		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) {
					enemyInfo.add(new Enemy(i, j));
				}
			}
		}
		
		int answer = 0;
		
		for (int i = 0; i < M; ++i) {
			for (int j = i; j < M; ++j) {
				for (int k = j; k < M; ++k) {
					// 복사
					List<Enemy> tempEnemy = new ArrayList<Enemy>();
					for (Enemy e : enemyInfo) {
						tempEnemy.add(new Enemy(e.i, e.j));
					}
					int cnt = attack(tempEnemy, new int[] {i, j, k});
					answer = (answer < cnt) ? cnt : answer;
				}
			}
		}
		
		System.out.println(answer);
	}
	
	public static int attack(List<Enemy> enemy, int[] pos) {
		int cnt = 0;
		
		while (!enemy.isEmpty()) {
			List<Enemy> killEnemy = new ArrayList<Enemy>();
			
			// 죽일 적 찾고
			for (int p : pos) {
				int ePos = getEnemy(enemy, p);
				
				if (ePos != -1) {
					killEnemy.add(enemy.get(ePos));
				}
			}
			
			// 죽이고
			for (Enemy e : killEnemy) {
				if (enemy.remove(e)) {
					cnt++;
				}
			}
			
			// 적들 이동
			for (int i = 0; i < enemy.size(); ++i) {
				Enemy e = enemy.get(i);
				e.i += 1;
				
				if (e.i == N) {
					enemy.remove(i);
					i--;
				}
			}
		}
		
		return cnt;
	}
	
	public static int getEnemy(List<Enemy> enemy, int pos) {
		int minDist = Integer.MAX_VALUE;
		int idx = Integer.MAX_VALUE;
		int minIdx = -1;
		
		for (int i = 0; i < enemy.size(); ++i) {
			Enemy e = enemy.get(i);
			
			int dist = N - e.i + Math.abs(pos - e.j);
			
			// 거리 체크
			if (dist > D) {
				continue;
			}
			
			if (dist < minDist) {
				minDist = dist;
				idx = e.j;
				minIdx = i;
			}
			else if (dist == minDist) {
				if (idx > e.j) {
					idx = e.j;
					minIdx = i;
				}
			}
		}
		
		return minIdx;
	}
}

---

pyo7410/Algorithm