백준 17135 자바 - 캐슬 디펜스

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

17135번: 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    private static int n, m, d;
    private static int map[][];
    private static List<int[]> list = new ArrayList<>();
    private static int[] archer = new int[3];
    private static int result;
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    list.add(new int[] {i, j});
                }
            }
        }

        locateArcher(0, 0);
        bw.write(String.valueOf(result));
        bw.flush();
    }

    private static void locateArcher(int idx, int start) {
        if (idx == 3) {
            List<int[]> data = copy(list);
            attackMonster(data);
            return;
        }
        for (int i = start; i < m; i++) {
            archer[idx] = i;
            locateArcher(idx + 1, i + 1);
        }
    }

    private static void attackMonster(List<int[]> list) {
        int count = 0;
        while (true) {
            if (list.isEmpty()) {
                break;
            }
            List<int[]> targets = new ArrayList<>();
            for (int i = 0; i < 3; i++) {
                PriorityQueue<Monster> queue = new PriorityQueue<>();

                for (int j = 0; j < list.size(); j++) {
                    int[] cur = list.get(j);
                    int curD = Math.abs(cur[0] - n) + Math.abs(cur[1] - archer[i]);
                    if (curD <= d) {
                        queue.add(new Monster(cur[0], cur[1], curD));
                    }
                }
                if (!queue.isEmpty()) {
                    Monster target = queue.poll();
                    boolean flag = false;
                    for (int k = 0; k < targets.size(); k++) {
                        int[] cur2 = targets.get(k);
                        if (target.x == cur2[0] && target.y == cur2[1]) {
                            flag = true;
                        }
                    }
                    if (!flag) {
                        targets.add(new int[] {target.x, target.y});
                    }
                }
            }
            for (int i = 0; i < targets.size(); i++) {
                for (int j = list.size() - 1; j >= 0; j--) {
                    if (targets.get(i)[0] == list.get(j)[0] && targets.get(i)[1] == list.get(j)[1]) {
                        list.remove(j);
                        count++;
                        break;
                    }
                }
            }
            for (int i = list.size() - 1; i >= 0; i--) {
                list.get(i)[0]++;
                if (list.get(i)[0] == n) {
                    list.remove(i);
                }
            }
        }
        result = Math.max(result, count);
    }

    private static List<int[]> copy(List<int[]> list) {
        List<int[]> temp = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            int[] cur = list.get(i);
            temp.add(new int[] {cur[0], cur[1]});
        }
        return temp;
    }

    private static class Monster implements Comparable<Monster> {
        int x;
        int y;
        int d;
        public Monster(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        @Override
        public int compareTo(Monster o) {
            if (this.d == o.d) return this.y - o.y;
            return this.d - o.d;
        }
    }
}

풀이

3명의 궁수의 자리를 배치한다. 배치 후 궁수의 사격 거리 중 가장 가까운 적, 그리고 가까운 적이 많다면 가장 왼쪽의 적을 우선적으로 제거한다. 이는 Comparable 을 구현한 Monster클래스와 PriorityQueue를 활용한다.