백준 - 17135 캐슬 디펜스(Java)

구현 문제입니다.

 

문제의 예제 입력 3번을 그림으로 표현하면 다음과 같습니다.

그림과 같이 성은 M개 만큼 존재하며, 해당 성 중에서 세 곳에만 궁수가 존재합니다.

즉, M개 중에서 세 곳에만 존재하기 때문에 조합을 사용하여 궁수의 위치를 결정할 수 있습니다.

조합으로 궁수의 위치를 결정하고, 게임을 진행하여 적을 제거 해 나아가는 완전탐색으로 접근하면 됩니다.

// 조합
private static void archerLocation(int r, int depth, boolean[] archers) {
    ...
}

 

적군에게 화살을 쏠 때 두 가지 방법이 필요합니다.

1. 궁수 시선의 이동
2. 궁수가 쏠 수 있는 범위

 

1. 궁수 시선의 이동

적군들은 시간이 지날 때 마다 아래로 움직입니다.

 

이런 방식으로 하려면, 배열 자체의 값을 전부 이동시켜야 합니다.

다른 방식으로, 턴이 지났을 때 적군을 움직이는 것이 아닌 궁수가 바라보는 시선을 바꾸면 됩니다.

시선을 위로 올립니다.

코드 상으로는 다음과 같습니다.

private static int doGame(List<Integer> locations) {
    // 턴이(Turn)이 지날 때 마다, 시선의 위치인 i를 위로 올림
    for(int i=n-1; i>=0; i--){
    	...
    }
}

 

2. 궁수가 쏠 수 있는 범위

아래 그림과 같이 세 번째 위치에 궁수가 있고, 궁수가 쏠 수 있는 범위를 4라 하겠습니다. (아래 그림이 잘못 되었습니다...)

해당 조건에서 첫 번째 턴에서 궁수가 쏠 수 있는 범위를 직선으로 표현하면 다음과 같습니다.

두 번째 턴과 세 번째 턴은 다음과 같습니다.

 

궁수가 바라보는 시선을 i, 범위를 d라고 하면 (i-d+1) ~ i까지가 화살을 쏠 수 있는 허용 세로 범위이게 됩니다.

for(int i=n-1; i>=0; i--){ // 시선
    ...
    for(int t = 0; t< ARCHER_NUMBER; t++){ // 궁수의 수 만큼 반복
        ...
        for(int x = i-d+1; x<=i; x++){ // 궁수가 쏠 수 있는 허용 세로 범위
            ...
        }
    }
}

 

세로 직선을 끝점을 기준으로

한 칸이 내려올 때 마다 가로가 좌, 우로 한 칸씩 커지는 것을 알 수 있습니다.

 

즉, 반복해서 내려올 때 마다, 반복한 개수만큼 가로가 증가합니다.

주의해야 할 점은 각 궁수의 y좌표와 허용 범위가 전체 범위를 넘어서면 안됩니다.

int ay = locations.get(t); // 각 궁수의 가로(y)좌표

for(int x = i-d+1; x<=i; x++){ // 궁수가 쏠 수 있는 허용 세로 범위
    loop++;
    if(x<0) continue;
    
    int firstRange = (ay-loop < 0) ? 0 : ay-loop; // 범위를 벗어나지 않게 조절
    int lastRange = (ay+loop > m-1) ? m-1 : ay+loop;

    for(int y= firstRange; y<=lastRange; y++){ // 궁수가 쏠 수 있는 허용 가로 범위
        if(copied[x][y] == 1){ // 적군이 있으면
            ...
        }
    }
}

 

[구현 코드]

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

public class Main {
    private static final String SEPARATOR = " ";
    private static final int ARCHER_NUMBER = 3;

    private static int[][] enemies;
    private static int n, m, d, answer, totalEnemies;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), SEPARATOR);

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        d = Integer.parseInt(stz.nextToken());

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

                if(enemies[i][j] == 1) totalEnemies++;
            }
        }

        archerLocation(ARCHER_NUMBER, 0, new boolean[m]);

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    // 조합
    private static void archerLocation(int r, int depth, boolean[] archers) {
        if(r == 0){
            // archers가 true이면 해당 위치에 궁수가 있다는 것임
            List<Integer> locations = new ArrayList<>();
            for(int i=0; i<m; i++){
                if (archers[i]) locations.add(i);
            }

            int aliveEnemy = doGame(locations);

            answer = Math.max(answer, totalEnemies - aliveEnemy);
            return;
        }

        if(depth == m) return;

        archers[depth] = true;
        archerLocation(r-1, depth + 1, archers);

        archers[depth] = false;
        archerLocation(r, depth + 1, archers);
    }

    private static int doGame(List<Integer> locations) {

        // 초기 입력을 복사함
        int[][] copied = copyEnemies();

        // 턴이(Turn)이 지날 때 마다, 시선의 위치인 i를 위로 올림
        for(int i=n-1; i>=0; i--){
            List<Enemy> inRangeEnemy = new ArrayList<>();

            for(int t = 0; t< ARCHER_NUMBER; t++){ // 궁수의 수 만큼 반복
                int loop = -1;
                int ay = locations.get(t); // 각 궁수의 가로(y)좌표

                for(int x = i-d+1; x<=i; x++){ // 궁수가 쏠 수 있는 허용 세로 범위
                    loop++;
                    if(x<0) continue;

                    int firstRange = (ay-loop < 0) ? 0 : ay-loop; // 범위를 벗어나지 않게 조절
                    int lastRange = (ay+loop > m-1) ? m-1 : ay+loop;

                    for(int y= firstRange; y<=lastRange; y++){ // 궁수가 쏠 수 있는 허용 가로 범위
                        if(copied[x][y] == 1){ // 적군이 있으면
                            // 가까운 적 부터 쏠 수 있게 거리를 계산해서 저장함
                            int dis = Math.abs(d- loop) + Math.abs(ay - y);
                            inRangeEnemy.add(new Enemy(x, y, dis, t));
                        }
                    }
                }
            }

            // 가까운 적부터 쏠 수 있게 정렬함
            sortNearestEnemyByArchers(inRangeEnemy);

            // 각 궁수가 가장 가까운 적을 쏨
            shooting(copied, inRangeEnemy);
        }

        // 게임이 끝나고 살아있는 적의 수 반환
        return getAliveEnemy(copied);
    }

    private static void sortNearestEnemyByArchers(List<Enemy> inRangeEnemy) {
        // 궁수들의 범위 내에 있는 적을 가까운 순으로 정렬함
        // 몇 번째 궁수가 쏠 지는 inRangeEnemy객체 내부에 archer값으로 저장되어 있음
        inRangeEnemy.sort((o1, o2) -> {
            if (o1.dis == o2.dis) return o1.y - o2.y;
            return o1.dis - o2.dis;
        });
    }

    private static void shooting(int[][] copied, List<Enemy> inRangeEnemy) {
        // 이전에 화살을 발사한 궁수가 또다시 쏘지 않게 함
        boolean[] isArcherShooting = new boolean[ARCHER_NUMBER];

        // inRangeEnemy는 각 궁수가 쏠 수 있는 적군의 위치임
        // 궁수는 같은 시간에 한 발만 쏠 수 있음. 때문에, isArcherShooting로 궁수가 쏘지 않았는지 확인
        for (Enemy candi : inRangeEnemy) {
            if (!isArcherShooting[candi.archer]) {
                copied[candi.x][candi.y] = 0;
                isArcherShooting[candi.archer] = true;
            }
        }
    }

    private static int getAliveEnemy(int[][] copied) {
        return (int) Arrays.stream(copied)
                .flatMapToInt(Arrays::stream)
                .filter(e -> e == 1)
                .count();
    }

    private static int[][] copyEnemies(){
        int[][] copied = new int[n][m];
        for(int i=0; i<n; i++){
            copied[i] = Arrays.copyOf(enemies[i], m);
        }
        return copied;
    }

    // archer는 해당 적군을 쏠 수 있는 궁수임
    private static class Enemy{
        int x, y, dis, archer;

        public Enemy(int x, int y, int dis, int archer) {
            this.x = x;
            this.y = y;
            this.dis = dis;
            this.archer = archer;
        }
    }
}