[알고리즘] 캐슬 디펜스

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

17135번: 캐슬 디펜스

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] map;
	static int[][] copyMap;
	static List<Point> enemies;
	static int[] positions;
	static List<int[]> positionsCombination = new ArrayList<>();
	static int time;
	static int count;
	static int N;
	static int M;
	static int D;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		
		enemies = new ArrayList<>();
		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) {
					enemies.add(new Point(i, j));
				}
			}
		}
		
		//  조합 MC3;
		
		List<Point> copyEnemies = new ArrayList<>();
		
		for (int i = 0; i < enemies.size(); i++) {
			copyEnemies.add(new Point(enemies.get(i).x, enemies.get(i).y));
		}
		positions = new int[3];
		Combination(0, 0);
		int maxCount = Integer.MIN_VALUE;
		for (int[] points : positionsCombination) {
			enemies = new ArrayList<>();
			for (int i = 0; i < copyEnemies.size(); i++) {
				enemies.add(new Point(copyEnemies.get(i).x, copyEnemies.get(i).y));
			}
			count = 0;
			time = 0;
			while(turn(points)) {
				time++;
			}
			maxCount = Math.max(maxCount, count);	
		}
		
		System.out.println(maxCount);
	}
	private static void Combination(int depth, int start) {
		if (depth == 3) {
			int[] temp = new int[3];
			for (int i = 0; i < 3; i++) {
				temp[i] = positions[i];
			}
			positionsCombination.add(temp);
			return;
		}
		for (int i = start; i < M; i++) {
			positions[depth++] = i;
			Combination(depth, i+1);
			depth--;
		}
	}
	private static boolean turn(int[] positions) {
		Set<Integer> set = new HashSet<>();
		for (int position : positions) {
			int x = N;
			int y = position;
			int minDistance = Integer.MAX_VALUE;
			int attackIndex = -1;
			for (int i = 0; i < enemies.size(); i++) {
				Point enemyPoint = enemies.get(i);
				int distance = Math.abs(x - enemyPoint.x) + Math.abs(y - enemyPoint.y);
				if (distance <= D) {
					if (distance < minDistance) {
						minDistance = distance;
						attackIndex = i;
					} else if (distance == minDistance) {
						if (enemies.get(attackIndex).y - enemyPoint.y > 0) {
							attackIndex = i;
						}
					}
				}
			}
			if (minDistance != Integer.MAX_VALUE) {
				set.add(attackIndex);
			}	
		}
		
		List<Point> deleteList = new ArrayList<>();
		for (int index : set) {
			count++;
			deleteList.add(enemies.get(index));
		}
		for (Point dPoint : deleteList) {
			enemies.remove(dPoint);
		}
		
		List<Point> newList = new ArrayList<>();
		for (int i = 0; i < enemies.size(); i++) {
			Point point = enemies.get(i);
			if (point.x + 1 == N) {
				continue;
			}
			point.x += 1;
			newList.add(point);
			
		}
		
		enemies = newList;
		if (enemies.size() > 0) {
			return true;
		}
		return false;
		
	}
}

나의 풀이

- List 원본을 만들때 그 안에 있는 Point 객체도 새로 만들어 줘야 하는데 새로 만들어 주지 않아서 원하는 값이 제대로 나오지 않았다.

- List를 복사할 때 안에 primitive type이 아닌 객체가 있다면 이를 염두에 두고 하자.

- 다른 방법으로는 복사 생성자를 이용한 방법도 있다고 한다.