[BOJ] 17135. 캐슬 디펜스

https://www.acmicpc.net/problem/17135

접근 방법

그대로 구현을 해주면 된다.

궁수의 위치에 따라서 조합을 써서 배열에 궁수의 위치를 넣어주었다.

static void sortArcher(int[] arr, boolean[] visited, int depth, int r) {
        if (r == 0) {
            tempMap = new boolean[N+1][M];
            archers = new ArrayList<>();
            for(int i=0; i<N; i++){
                tempMap[i] = map[i].clone();
            }
            for(int i=0; i<M; i++){
                if( visited[i] ) archers.add(i);
            }
                        // solve는 궁수의 위치에 따라서 적을 죽인 값을 가지고
            ans = Math.max(ans,solve());
            return;
        }

        if (depth == M) {
            return;
        }

        visited[depth] = true;
        sortArcher(arr, visited, depth + 1, r - 1);

        visited[depth] = false;
        sortArcher(arr, visited, depth + 1, r);
    }

        static int solve() {
                tempAns = 0;

                while(true){

                    if(isEnd()) return tempAns;

                    attackEnemy();

                    tempMap = movingEnemy();
                }
            }

또한 궁수들이 일제히 공격을 했을 때의 코드이다.

static void attackEnemy(){
        boolean[][] cloneMap = new boolean[N][M];

        for(int i=0; i<N; i++){
            cloneMap[i] = tempMap[i].clone();
        }
        ArrayList<ArcherRange> finalArcherAttack = new ArrayList<>();
        for(int i=0; i<archers.size(); i++){
            Location archersLocation = new Location(N, archers.get(i));
            ArrayList<ArcherRange> archerRanges = new ArrayList<>();
            for(int k=0; k<N; k++){
                for(int z = 0; z<M; z++){
                    if(cloneMap[k][z]) {
                        int distance = getDistance(archersLocation, new Location(k, z));
                        if (distance <= D) {
                            archerRanges.add(new ArcherRange(k, z, distance));
                        }
                    }
                }
            }
            if(archerRanges.size() != 0){
                Collections.sort(archerRanges);
                finalArcherAttack.add(archerRanges.get(0));
            }
        }
        for(int i=0; i<finalArcherAttack.size(); i++){
            int x = finalArcherAttack.get(i).x;
            int y = finalArcherAttack.get(i).y;
            if(!tempMap[x][y]) continue;
            tempMap[x][y] = false;
            tempAns++;
        }

    }

Need Know

1. 구현!

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N;
    static int M;
    static int D;
    static boolean[][] map;
    static boolean[][] tempMap;
    static int tempAns;
    static ArrayList<Integer> archers;
    static int[] archer;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        set();
        bw.write(ans +"");

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

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        map = new boolean[N][M];
        archer = new int[M];
        boolean[] visited = new boolean[M];

        for(int i=0; i<M; i++){
            archer[i] = i;
        }

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

        sortArcher(archer,visited ,0,3);
    }

    static int solve() {
        tempAns = 0;

        while(true){

            if(isEnd()) return tempAns;

            attackEnemy();

            tempMap = movingEnemy();
        }
    }
    static void sortArcher(int[] arr, boolean[] visited, int depth, int r) {
        if (r == 0) {
            tempMap = new boolean[N+1][M];
            archers = new ArrayList<>();
            for(int i=0; i<N; i++){
                tempMap[i] = map[i].clone();
            }
            for(int i=0; i<M; i++){
                if( visited[i] ) archers.add(i);
            }

            ans = Math.max(ans,solve());
            return;
        }

        if (depth == M) {
            return;
        }

        visited[depth] = true;
        sortArcher(arr, visited, depth + 1, r - 1);

        visited[depth] = false;
        sortArcher(arr, visited, depth + 1, r);
    }

    static void attackEnemy(){
        boolean[][] cloneMap = new boolean[N][M];

        for(int i=0; i<N; i++){
            cloneMap[i] = tempMap[i].clone();
        }
        ArrayList<ArcherRange> finalArcherAttack = new ArrayList<>();
        for(int i=0; i<archers.size(); i++){
            Location archersLocation = new Location(N, archers.get(i));
            ArrayList<ArcherRange> archerRanges = new ArrayList<>();
            for(int k=0; k<N; k++){
                for(int z = 0; z<M; z++){
                    if(cloneMap[k][z]) {
                        int distance = getDistance(archersLocation, new Location(k, z));
                        if (distance <= D) {
                            archerRanges.add(new ArcherRange(k, z, distance));
                        }
                    }
                }
            }
            if(archerRanges.size() != 0){
                Collections.sort(archerRanges);
                finalArcherAttack.add(archerRanges.get(0));
            }
        }
        for(int i=0; i<finalArcherAttack.size(); i++){
            int x = finalArcherAttack.get(i).x;
            int y = finalArcherAttack.get(i).y;
            if(!tempMap[x][y]) continue;
            tempMap[x][y] = false;
            tempAns++;
        }

    }

    static boolean[][] movingEnemy(){
        boolean[][] cloneMap = new boolean[N][M];

        for(int i=1; i<N; i++){
            cloneMap[i] = tempMap[i-1].clone();
        }
        return cloneMap;
    }

    static int getDistance(Location loc1, Location loc2){
        return Math.abs(loc1.x - loc2.x) + Math.abs(loc1.y - loc2.y);
    }

    static boolean isEnd(){
        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                if(tempMap[i][k]) return false;
            }
        }
        return true;
    }
}
class Location{
    int x,y;

    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class ArcherRange implements Comparable<ArcherRange>{
    int x,y,distance;

    public ArcherRange(int x, int y, int distance) {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }

    @Override
    public int compareTo(ArcherRange o) {
        if(distance - o.distance == 0){
            return y - o.y;
        }else{
            return distance - o.distance;
        }
    }
}