BOJ 17135 캐슬 디펜스

https://www.acmicpc.net/problem/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은 적이 있는 칸이다.

---

출력

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

---

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

---

예제 입력 1

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

예제 출력 1

3

예제 입력 2

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

예제 출력 2

3

… 이하 예제 생략

---

코드

이번 문제도 시뮬레이션 문제였던 만큼 크게 어려운 부분 없이 단순 구현 문제였다.

다만, 구현에 조금 시간이 걸렸다.

이번 문제의 풀이 과정은 다음과 같다.

1. 조합으로 궁수를 배치할 3개의 성을 고른다.
2. 배치한 궁수의 위치를 기준으로 시뮬레이션을 진행한다.
3. 각 시뮬레이션들의 적 제거 수 중 최대 적 제거 수를 계산한다.

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

public class Main {

    static final int NUMBER_OF_ARCHERS = 3; // 배치할 궁수의 수
    static int maxKill = 0; // 최대 적 제거 수 (정답)
    static int N;
    static int M;
    static int D;
    static List<Point> enemies = new ArrayList<>();

    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++) {
                String input = st.nextToken();
                if(input.equals("1")) {
                    enemies.add(new Point(i, j));
                }
            }
        }
        
        search(0, 0);

        System.out.println(maxKill);
    }

    /**
     * 궁수를 배치할 성의 위치를 조합으로 골라 시뮬레이션해보는 메소드
     * @param castle 뽑기 시작할 성의 위치
     * @param selectedCastles 선택한 성의 위치를 표현한 비트마스크
     */
    static void search(int castle, int selectedCastles) {
        // 전부 뽑았을 경우, 시뮬레이션 실행
        if(Integer.bitCount(selectedCastles) == NUMBER_OF_ARCHERS) {
            simulate(selectedCastles);
            return;
        }

        for (int i = castle; i < M; i++) {
            search(i + 1, selectedCastles | 1 << i);
        }
    }

    /**
     * 시뮬레이션을 진행하고, 그 결과 제거한 적의 최대 수를 갱신하는 메소드
     * @param archersPosition 궁수를 배치한 위치를 나타내는 비스마스크
     */
    static void simulate(int archersPosition) {
        int kill = 0;
        List<Point> simulationEnemies = deepCopyOf(enemies);
        
        while (!simulationEnemies.isEmpty()) {
            // 궁수의 공격 턴을 진행하여 적을 제거하고, 처치한 수를 누적시킴
            kill += proceedArcherTurn(simulationEnemies, archersPosition);
            // 적의 이동 턴을 진행하고, 성에 다다른 적을 제거함
            proceedEnemyTurn(simulationEnemies);
        }
        
        // 최대 적 처치 수를 갱신
        maxKill = Integer.max(maxKill, kill);
    }

    /**
     * 궁수의 공격 턴을 진행하고, 처치한 적의 수를 반환하는 메소드
     * @param enemies 적들의 위치 정보
     * @param archersPosition 궁수를 배치한 위치를 나타내는 비스마스크
     * @return 처치한 적의 수
     */
    static int proceedArcherTurn(List<Point> enemies, int archersPosition) {
        List<Point> toKill = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            // D 이하의 거리에 있는 적들 중 최단 거리에 있는 적을 공격 대상 목록에 추가
            if((archersPosition & 1 << i) != 0) {
                Point targetEnemy = getTargetEnemy(enemies, i);

                // 공격할 수 있는 적이 존재하고, 공격 대상 목록에 있지 않은 경우 목록에 추가
                if(targetEnemy != null && !toKill.contains(targetEnemy)) {
                    toKill.add(targetEnemy);
                }
            }
        }

        // 공격 대상 목록에 있는 적들을 제거
        enemies.removeAll(toKill);
        return toKill.size();
    }

    /**
     * 공격 가능 범위 D 이내에 존재하며, 가장 가까이 존재하는 공격 대상 적을 반환하는 메소드
     * @param enemies 적들의 위치 정보
     * @param archerPosition 궁수를 배치한 위치를 나타내는 비스마스크
     * @return 적절한 공격 대상 적의 위치 정보
     */
    static Point getTargetEnemy(List<Point> enemies, int archerPosition) {
        int minDistance = Integer.MAX_VALUE;
        Point targetEnemy = null;

        for (int j = 0; j < enemies.size(); j++) {
            Point enemy = enemies.get(j);
            int distance = calculateDistance(archerPosition, enemy);
            // 궁수의 공격 가능 범위보다 멀리 있을 경우, 탐색 생략
            if(distance > D) {
                continue;
            }

            // 가장 가까이 있는 적 탐색 진행 (거리가 같은 경우, 더 왼쪽에 있는 적 선택)
            if(distance < minDistance) {
                minDistance = distance;
                targetEnemy = enemy;
            } else if(distance == minDistance && enemy.y < targetEnemy.y) {
                targetEnemy = enemy;
            }
        }
        return targetEnemy;
    }

    /**
     * 적들을 한 칸 전진시키는 메소드
     * @param enemies 적들의 위치 정보
     */
    static void proceedEnemyTurn(List<Point> enemies) {
        // 적들을 한 칸 전진시키고, 성에 도달한 적은 List에서 제외
        enemies.removeIf(enemy -> {
            enemy.x++;
            return enemy.x >= N;
        });
    }

    // 거리 계산 메소드
    static int calculateDistance(int archer, Point enemy) {
        return N - enemy.x + Math.abs(enemy.y - archer);
    }

    // List<Point>를 깊은 복사하여 반환하는 메소드
    static List<Point> deepCopyOf(List<Point> list) {
        List<Point> newList = new ArrayList<>();
        for (Point point: list) {
            newList.add(new Point(point));
        }

        return newList;
    }
}