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

🧪 17135 캐슬 디펜스

---

난이도 : 🌟 골드 3
유형 : 그래프 탐색 (BFS)

17135번: 캐슬 디펜스

 

📝 문제

---

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

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

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

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

 

입력

 

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

 

출력

 

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

🚧  주의할 점

---

1. 같은 적이 여러 궁수에게 공격 당할 수 있다. → 큰 문제가 아니라고 생각했지만 첫번째 궁수가 잡은 적을 두번째 궁수가 제외하면 안된다.

 

2. 얕은 복사와 깊은 복사 주의

 

🧐 핵심 로직

---

◈  궁수를 배치해준다. → 조합을 통해 모든 배치를 탐색하는 것 말고 다른 방법이 없을지 생각했지만 모든 배치 탐색 이외의 방식이 생각나지 않았다.

◈  우선순위 큐를 활용하여 가장 가깝고, 여러 적이 가깝다면 가장 왼쪽 적이 제거되도록 구현

◈  적들 리스트와 제거될 리스트를 비교하여 제거한 후 적들 리스트 행 한칸씩 늘리고 성에 닿은 적들은 제거해주는 방식으로 반복을 진행한다.

 

💻 최종 코드 (452 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static int n, m, dist, res;
    static int[] archer;
    static int[][] castleMap;
    static List<int[]> monsterGroup;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static class Node implements Comparable<Node> {

        int x, y, d;

        Node(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        @Override
        public int compareTo(Node o) {
            if (this.d == o.d) { // 거리가 같다면
                return this.y - o.y; // 열이 더 작은 값(더 왼쪽)
            } else
                return this.d - o.d; // 오름차순
        }
    }

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        dist = Integer.parseInt(st.nextToken());

        archer = new int[3];
        monsterGroup = new ArrayList<>();
        castleMap = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                castleMap[i][j] = Integer.parseInt(st.nextToken());

                if (castleMap[i][j] == 1) {
                    monsterGroup.add(new int[]{i, j});
                }
            }
        }

        locateArcher(0, 0);

        System.out.println(res);

        br.close();
    }

    private static void locateArcher(int index, int start) {
        if (index == 3) {
            List<int[]> newMonsterGroup = copy(monsterGroup);
            action(newMonsterGroup);
            return;
        }

        for (int i = start; i < m; i++) {
            archer[index] = i;
            locateArcher(index + 1, i + 1);
        }
    }

    private static List<int[]> copy(List<int[]> monsterGroup) {
        List<int[]> tmp = new ArrayList<>();

        for (int[] cur : monsterGroup) {
            tmp.add(new int[]{cur[0], cur[1]});
        }

        return tmp;
    }

    private static void action(List<int[]> newMonsterGroup) {
        int cnt = 0;

        while (!newMonsterGroup.isEmpty()) {
            List<int[]> targets = new ArrayList<>();

            for (int i = 0; i < 3; i++) {
                PriorityQueue<Node> pq = new PriorityQueue<>();

                for (int j = 0; j < newMonsterGroup.size(); j++) {
                    int[] cur = newMonsterGroup.get(j);
                    int diffDist = Math.abs(cur[0] - n) + Math.abs(cur[1] - archer[i]);
                    if (diffDist <= dist) {
                        pq.add(new Node(cur[0], cur[1], diffDist));
                    }
                }

                if (!pq.isEmpty()) {
                    Node target = pq.poll();
                    boolean flag = false;
                    for (int j = 0; j < targets.size(); j++) {
                        int[] cur2 = targets.get(j);
                        if (cur2[0] == target.x && cur2[1] == target.y) {
                            flag = true;
                            break;
                        }
                    }

                    if (!flag) {
                        targets.add(new int[]{target.x, target.y});
                    }
                }
            }

            for (int i = 0; i < targets.size(); i++) {
                for (int j = newMonsterGroup.size() - 1; j >= 0; j--) {
                    if (targets.get(i)[0] == newMonsterGroup.get(j)[0] && targets.get(i)[1] == newMonsterGroup.get(j)[1]) {
                        newMonsterGroup.remove(j);
                        cnt++;
                        break;
                    }
                }
            }

            for (int i = newMonsterGroup.size() - 1; i >= 0; i--) {
                newMonsterGroup.get(i)[0] += 1;
                if (newMonsterGroup.get(i)[0] == n)
                    newMonsterGroup.remove(i);
            }
        }

        res = Math.max(res, cnt);
    }
}