링크

17135 캐슬 디펜스

문제

풀이

이 문제는 적이 한턴마다 한칸씩 내려오고 궁수 3명을 적절하게 배치해서 적을 최대한 많이 잡는 게임이다.
궁수는 N번행의 바로 아래의 칸에 성이 있고 성에만 배치할 수 있다.
적이 성에 도달하면 사라진다.
그리고 궁수는 적과의 거리가 D이하인 적 중에서 가장 가까운 적을 공격하고 여러명일 경우 가장 왼쪽을 공격한다.
같은 적이 여러 궁수에게 동시에 공격당할 수 있다.

조건이 상당히 까다로운데 천천히 해결하면 된다.

나의 로직 순서는
1. 맵을 입력받는다.
2. 궁수의 위치를 백트래킹을 통해서 궁수 3명을 배치한다.
3. 맵을 복사해두고 궁수와 적 위치를 비교해 가장 가깝고 왼쪽인 친구를 찾는다
4. 적은 동시에 공격을 받을 수 있다고 했으니 공격받은 적의 좌표를 저장해두고 궁수3명이 공격이 끝나면 복사한 맵을 바꾼다.
5. 맵에 적이 있는지 확인하고 없으면 2번, 적이 있으면 3번을 반복한다.

나는 궁수와 가장 가깝고 왼쪽인 값을 찾기 위해 우선순위 큐를 사용하여 거리순으로 내림차순 x좌표 내림차순으로 가장 가까운 적을 뽑아냈다.
그리고 궁수들이 공격할 좌표들을 list에 저장해서 한번에 copyMap을 수정하고 한칸 내렸다.

코드

import java.awt.desktop.PreferencesEvent;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.nio.Buffer;
import java.sql.Array;
import java.util.*;

public class Main {
    public static int n, m, d, answer;
    public static int[][] map;
    public static int[][] copyMap;

    static class Enemy implements Comparable<Enemy>{
        int x;
        int y;
        int dis;

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

        @Override
        public int compareTo(Enemy o){
            if(this.dis == o.dis){
                return this.y - o.y;
            }

            return this.dis - o.dis;
        }

        @Override
        public String toString() {
            return "Enemy{" +
                    "x=" + x +
                    ", y=" + y +
                    ", dis=" + dis +
                    '}';
        }
    }


    public static void main(String[] args) throws Exception {
        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());

        map = new int[n+1][m];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

//        System.out.println("------------------");
//        for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(map[i]));
//
//        down();
//        System.out.println("-----------------------");
//        for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(map[i]));





        dfs(0, 0);
        System.out.println(answer);

    }

    public static void dfs(int dept, int cnt){
        if(cnt == 3 || dept >= m){
            if(cnt < 3) return;

            copyMap = new int[map.length][map[0].length];
            for(int i=0;i<map.length;i++){
                for(int j=0;j<map[0].length;j++){
                    copyMap[i][j] = map[i][j];
                }
            }
//            System.out.println("-----------------------");
//            for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(copyMap[i]));

            int count = attack();
//            System.out.println(count);
            answer = Math.max(count, answer);

            return;
        }

        //궁수 배치
        map[n][dept] = 2;
        dfs(dept+1, cnt+1);
        map[n][dept] = 0;

        //궁수 배치 x
        dfs(dept+1, cnt);
    }

    //궁수가 공격하는 적
    //여러개있으면 가장 왼쪽인거
    public static int attack(){
        int count = 0;
//        System.out.println("attack");

        boolean[] ashes = new boolean[m];
        for(int i=0;i<map[0].length;i++){
            if(copyMap[n][i] != 0){
                ashes[i] = true;
            }
        }

        while(true){
//            System.out.println("while");
            //적이 없으면 게임 종료
            if(checkEnemy()){
                return count;
            }

            List<Enemy> list = new ArrayList<>();
            for(int i=0;i<map[0].length;i++){
                if(list.size() == 3) break;

                if(copyMap[n][i] != 0){
                    Enemy enemy = find(n, i);
//                    System.out.println("enemy = " + enemy);
                    if(enemy.dis <= d)
                        list.add(enemy);
                }
            }
//            System.out.println(list);

            //적 제거
            for(Enemy element : list){
                if(copyMap[element.x][element.y] == 1){
                    copyMap[element.x][element.y] = 0;
                    count++;
                }
            }

            //내리기
            down();
//            System.exit(0);
//            System.out.println("----------- 내림 -----------------");
//            for(int i=0;i<map.length;i++) System.out.println(Arrays.toString(copyMap[i]));


        }



    }

    //가장 가까운거리, 만약 같은 거리에 있으면 왼쪽꺼부터터
    public static Enemy find(int asheX, int asheY){
        Queue<Enemy> queue = new PriorityQueue<>();

//        System.out.println("ashx = " + asheX + " ashey = " + asheY);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(copyMap[i][j] == 1){
                    queue.add(new Enemy(i, j, Math.abs(i - asheX) + Math.abs(j - asheY)));
                }
            }
        }

//        for(int i=0;i<queue.size();i++){
//            System.out.println(queue.poll());
//        }

        Enemy catchEnemy = queue.poll();
//        System.out.println(catchEnemy);

//        if(catchEnemy <= d){
//            return true;
//        }

        return catchEnemy;
    }

    public static boolean checkEnemy(){

        for(int i=0;i<copyMap.length-1;i++){
            for(int j=0;j<copyMap[i].length;j++){
                if(copyMap[i][j] == 1){
                    return false;
                }
            }
        }

        return true;
    }

    //1초 후 떨어지는 적
    public static void down(){
        //map[끝][j] = map[끝-1][j]

        for(int i=n-1;i>0;i--){
            for(int j=0;j<m;j++){
                copyMap[i][j] = copyMap[i-1][j];
            }
        }

        //맨위 0으로 셋팅
        for(int i=0;i<m;i++){
            copyMap[0][i] = 0;
        }

    }

}