[백준 : 골드 3] Java BJ17135 캐슬 디펜스

 #️⃣문제

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

 

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

 

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

 

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

---

#️⃣ 입력

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

 

#️⃣ 출력

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

---

✅ 풀이 Point

1️⃣ 게임 진행 순서

💡궁수와의 거리가 D 이하인 적 중에 거리가 가장 짧은 적 공격
    →  거리가 가장 짧은 적이 여러 명인 경우 가장 왼쪽의 적 공격
  우선 순위 : 거리 → 좌측에 위치한 적

• 궁수 3명 동시에 공격
  → 적 아래로 한 칸 이동(이동한 칸이 성일 경우 해당 적 제외)

 

2️⃣ 궁수의 배치에 따라 적을 죽일 수 있는 최대치가 다르기 때문에 궁수의 배치 조합을 구해야 함.

• 궁수의 수 3명 고정 → R = 3
• int[ ] order = new int[R] → 궁수 3명의 x 좌표가 든 배열
• 재귀로 구현, 재귀로 넘어갈 때 idx를 같이 넘겨서 중복 방지

private static void comb(int k, int s) { // 15 * 14 * 13 / 6 = 455 충분히 가능함.
    if (R == k) {
        ans = Math.max(ans, solution());
    } else {
        for (int i = s; i < M; i++) {
            order[k] = i;
            comb(k + 1, i + 1);
        }
    }
}

 

3️⃣ 각 궁수가 죽일 수 있는 가능한 모든 적을 아래와 같은 정렬 기준을 가진 우선순위 큐에 넣어서 가장 죽일 가능성이 높은 적을 0번 인덱스에 위치하게 함.

• class Node / 1순위 : 궁수와 적의 거리 오름차순, 2순위 : 적의 x좌표 오름차순

static class Node implements Comparable<Node> {
    int i;
    int j;
    int d; // 가중치

    public Node(int i, int j, int d) {
        this.i = i;
        this.j = j;
        this.d = d;
    }

    @Override
    public int compareTo(Node o) {
        if (this.d == o.d) return this.j - o.j; // 거리가 같다면 더 왼쪽에 위치한 것으로 정렬
        return this.d - o.d;
    }
}

• enemyCandidates가 존재하면 가장 앞의 원소를 빼서 해당 턴에 실제로 궁수가 죽일 적이 들어가는 enemies 배열에 넣어줌.

List<Node> enemies = new ArrayList<>();
for (int k = 0; k < R; k++) {
    PriorityQueue<Node> enemyCandidates = new PriorityQueue<>(); // 각 궁수가 죽일 수 있는 적 후보
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // 적이 존재하고 적과의 거리 D 이하일 때,
            if (arrSol[i][j] == 1) {
                if (((N - i) + Math.abs(order[k] - j)) <= D) {
                    enemyCandidates.offer(new Node(i, j, (N - i) + Math.abs(order[k] - j)));
                }
            }
        }
    }

    if (!enemyCandidates.isEmpty()) {
        Node node = enemyCandidates.poll();
        enemies.add(node);
    }
}

 

• 중복된 적을 죽일 수 있으므로 enemies 배열의 적을 제거하기 전에 현재 배열에 적이 존재하는지 확인 필요함.

for (Node enemy : enemies) { // 궁수, 적 제거
    if (arrSol[enemy.i][enemy.j] == 1) {
        arrSol[enemy.i][enemy.j] = 0;
        cnt++;
    }
}

 

4️⃣ 적 제거 과정까지 거친 후 적이 이동하고 arrSol에 적이 남아있어 위의 과정을 반복해야하는지 확인.

boolean temp = false; // arrSol에 적이 아직 남아있어 while문을 반복해야하는지 판단
for (int j = 0; j < M; j++) arrSol[N - 1][j] = 0;
for (int i = N - 2; i > -1; i--) { // 적 아래로 한 칸 이동
    for (int j = 0; j < M; j++) {
        if (arrSol[i][j] == 1) {
            arrSol[i][j] = 0;
            arrSol[i + 1][j] = 1;
            temp = true;
        }
    }
}

 

✅ 정답

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

public class Main {
    static int N, M, D;
    static int R = 3; // 조합 mCr
    static int[][] arr;
    static int[] order; // 궁수의 x좌표를 담은 배열
    static int ans = 0;

    static class Node implements Comparable<Node> {
        int i;
        int j;
        int d; // 가중치

        public Node(int i, int j, int d) {
            this.i = i;
            this.j = j;
            this.d = d;
        }

        @Override
        public int compareTo(Node o) {
            if (this.d == o.d) return this.j - o.j; // 거리가 같다면 더 왼쪽에 위치한 것으로 정렬
            return this.d - o.d;
        }
    }

    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());
        arr = new int[N][M];
        order = new int[R];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }

        comb(0, 0);
        System.out.println(ans);
    }

    private static void comb(int k, int s) { // 15 * 14 * 13 / 6 = 455 충분히 가능함.
        if (R == k) {
            ans = Math.max(ans, solution());
        } else {
            for (int i = s; i < M; i++) {
                order[k] = i;
                comb(k + 1, i + 1);
            }
        }
    }

    private static int solution() {
        // 원본 배열 유지를 위한 복사
        int[][] arrSol = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) arrSol[i][j] = arr[i][j];
        }

        int cnt = 0;
        boolean flag = true;
        while (flag) {
            List<Node> enemies = new ArrayList<>();
            for (int k = 0; k < R; k++) {
                PriorityQueue<Node> enemyCandidates = new PriorityQueue<>(); // 각 궁수가 죽일 수 있는 적 후보
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        // 적이 존재하고 적과의 거리 D 이하일 때,
                        if (arrSol[i][j] == 1) {
                            if (((N - i) + Math.abs(order[k] - j)) <= D) {
                                enemyCandidates.offer(new Node(i, j, (N - i) + Math.abs(order[k] - j)));
                            }
                        }
                    }
                }

                if (!enemyCandidates.isEmpty()) {
                    Node node = enemyCandidates.poll();
                    enemies.add(node);
                }
            }

            for (Node enemy : enemies) { // 궁수, 적 제거
                if (arrSol[enemy.i][enemy.j] == 1) {
                    arrSol[enemy.i][enemy.j] = 0;
                    cnt++;
                }
            }

            boolean temp = false; // arrSol에 적이 아직 남아있어 while문을 반복해야하는지 판단
            for (int j = 0; j < M; j++) arrSol[N - 1][j] = 0;
            for (int i = N - 2; i > -1; i--) { // 적 아래로 한 칸 이동
                for (int j = 0; j < M; j++) {
                    if (arrSol[i][j] == 1) {
                        arrSol[i][j] = 0;
                        arrSol[i + 1][j] = 1;
                        temp = true;
                    }
                }
            }

            if (!temp) {
                flag = false;
            }
        }

        return cnt;
    }
}