[백준] 17135. 캐슬 디펜스 (시뮬레이션/Java)

[BOJ] 17135. 캐슬 디펜스

 

📌 풀이 과정

캐슬 디펜스 문제 조건

• 각 궁수는 공격 범위 내에서 가장 가까운 적을 공격하며, 동일한 거리의 적이 여러 명일 경우 가장 왼쪽의 적을 선택한다.
• 매 턴마다 모든 궁수가 동시에 공격하고, 공격받은 적은 제거된다. 공격 후, 살아남은 적은 한 칸 아래로 이동한다.
• 적이 성에 도달하면 게임에서 제외된다.

 

문제 설계하기

1. 적의 위치를 리스트에 저장해, 공격할 대상을 관리한다.

2. 3명의 궁수를 성이 있는 칸에 배치하는 조합을 만든다.

3. 배치 완료된 각 궁수의 위치에 대해 가능한 적을 탐색한다.

• 적의 위치와 궁수의 거리 계산 → 맨해튼 거리
• 가장 가까운 적을 찾고, 동일한 거리에 여러 적이 있다면 가장 왼쪽 열에 있는 적을 선택한다.

4. 적 제거 및 이동하기

• 궁수들이 선택한 적을 제거한다. 이때, 중복 방지를 위해 공격한 적의 위치를 기록한다.
• 공격 후 남아있는 적은 한칸 아래로 이동한다. (성에 도달한 적은 제거)

5. 각 턴이 끝날때마다 최대로 제거된 적 수를 업데이트 한다.

 

 

✨ 제출 코드

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

/**
 * 메모리 : 42836	KB
 * 시간 : 348 ms
 */
public class Main {

    static int N, M, D, answer;
    static List<Node> enemies = new ArrayList<>(); // 적의 위치를 저장하는 리스트

    private static class Node {
        int x, y;

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

    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()); // 궁수의 공격 거리 제한

        // 적의 위치를 저장
        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 Node(i, j));
                }
            }
        }

        pickArchers(0, 0, new int[3]);
        System.out.println(answer);
    }

    private static void pickArchers(int start, int count, int[] archers) {
        if (count == 3) {
            simulateGame(archers);
            return;
        }

        for (int i = start; i < M; i++) {
            archers[count] = i;
            pickArchers(i + 1, count + 1, archers);
        }
    }

    private static void simulateGame(int[] archers) {
        int killCount = 0; // 제거된 적의 수
        List<Node> currentEnemies = new ArrayList<>(enemies); // 현재 적 리스트 복사

        // 매 턴마다 적을 공격하고 이동
        for (int round = 0; round < N; round++) {
            boolean[][] attacked = new boolean[N][M]; // 공격한 적을 기록
            List<Node> targets = new ArrayList<>();

            for (int archer : archers) {
                Node target = null;
                int minDistance = Integer.MAX_VALUE;

                for (Node enemy : currentEnemies) {
                    int distance = (N - enemy.x) + Math.abs(archer - enemy.y); // 거리 계산
                    if (distance <= D) {
                        // 가장 가까운 적 및 왼쪽의 적 선택
                        if (distance < minDistance || (distance == minDistance && enemy.y < target.y)) {
                            minDistance = distance;
                            target = enemy;
                        }
                    }
                }

                if (target != null && !attacked[target.x][target.y]) {
                    targets.add(target);
                    attacked[target.x][target.y] = true; // 공격한 적 기록
                }
            }

            // 공격한 적 제거
            for (Node target : targets) {
                currentEnemies.remove(target); // 현재 적 리스트에서 제거
                killCount++;
            }

            // 적 이동
            List<Node> moveEnemies = new ArrayList<>();
            for (Node enemy : currentEnemies) {
                if (enemy.x + 1 < N) { // 아래로 이동 가능한 경우
                    moveEnemies.add(new Node(enemy.x + 1, enemy.y)); // 적 위치 업데이트
                }
            }
            currentEnemies = moveEnemies; // 현재 적 리스트 업데이트
        }

        answer = Math.max(answer, killCount);
    }
}