[백준, JAVA] boj 17135 캐슬디펜스 골드3

🔗 문제링크 🔗

17135번: 캐슬 디펜스

---

🌟 생각 흐름 🌟

1. 우선 궁수의 배치를 생각한다, 궁수는 DFS로 계산하여 3자리를 구하면 된다.
2. DFS로 배치 후에 해당 환경에서 궁수가 죽일 수 있는 최대 적의 수를 구한다.
   1. 모든 적에 대해서 궁수와의 거리를 비교한다.
   2. 만약 거리가 D이하이고 현재 궁수의 최소 거리의 적보다 가깝다면 교체한다.
      
      1. 최소 값 선택 기준
         1. 만약 현재 최소 값보다 작으면 교체한다.
         2. 만약 최소 값과 같은면 더 왼쪽에 있는 걸 선택한다
      2. 값 비교가 끝난이후에는 한 칸 이동한다. ( 가로축 기준 한 칸 아래로 내려온다)
   3. 모든 적에 대해서 비교한 이후에 최소값의 경우 isDie를 True로 변경하였다.(바로 삭제할 수도 있지만 플래그로 표시했다.) 
      1. isDieFlag가 참이라면 죽은것이므로 그 이후 턴부터는 해당 값을 죽인다.

배열 없이 객체로 풀었는데 배열로 푸는 경우가 효율성이 더 좋게 나오는 것 같았다.

---

🍳 코드 🍳

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

public class boj_17135_캐슬디펜스 {
    private static class Point {
        int x;
        int y;

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

        public int getDistance(Enemy cpyEnemy) {
            return Math.abs(x - cpyEnemy.x) + Math.abs(y - cpyEnemy.y);
        }
    }

    private static class Enemy extends Point {
        boolean isDie = false; //죽은 적을 표시했다.

        public Enemy(int x, int y) {
            super(x, y);
        }
    }

    private static int enemyCnt;
    private static int N, M, D; //행,열
    private static List<Enemy> enemies = new ArrayList<>();
    private static int maxDie = 0;
    private static int[] solider = new int[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        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 Enemy(i, j));
                    enemyCnt++;
                }
            }
        }

        findMaxCase(0, 0);
        System.out.println(maxDie);
    }

    private static void findMaxCase(int nowDepth, int start) {
        if (maxDie == enemyCnt) return;

        if (nowDepth == 3) { //궁수 3명의 위치
            List<Point> soliders = new ArrayList<>();

            for (int i : solider) {
                soliders.add(new Point(N, i));
            }

            playGame(soliders);
        } else {
            for (int i = start; i < M && maxDie < enemyCnt; i++) {
                solider[nowDepth] = i;
                findMaxCase(nowDepth + 1, i + 1);
            }
        }

    }

    private static void playGame(List<Point> soliders) {
        //setting enemy(적을 복사한다)
        LinkedList<Enemy> nowGameEnemy = new LinkedList<>();
        for (Enemy enemy : enemies) {
            nowGameEnemy.add(new Enemy(enemy.x, enemy.y));
        }

        int dieCnt = 0; //죽은 적의 숫자
        while (!nowGameEnemy.isEmpty()) {
            Enemy[] minEnemy = new Enemy[3];
            int[] minDistance = {D, D, D};
            
            int cc = 0; //index 현재 적 리스트의 위치
            while (cc < nowGameEnemy.size()) {
                Enemy tempEnemy = nowGameEnemy.get(cc);
                //3명의 궁수와 길이 비교
                if (tempEnemy.isDie) { //이미 죽은 적이면 제거하고 넘어간다.
                    nowGameEnemy.remove(cc);
                    dieCnt++;
                    continue;
                }
                if (tempEnemy.x == N) { //이미 성벽을 통과했으면 제거하고 넘어간다.
                    nowGameEnemy.remove(cc);
                    continue; //성을 통과함
                }

                for (int i = 0; i < 3; i++) { //3명의 궁수와 비교한다.
                    Point nowSolider = soliders.get(i);
                    int distance = nowSolider.getDistance(tempEnemy);
                    if (distance < minDistance[i] || //길이가 더 적은경우
                            (minEnemy[i] == null && distance <= minDistance[i]) //현재 선택된 적이 없는경우 D이하이면 무조건 넣는다
                            || (distance == minDistance[i] && tempEnemy.y < minEnemy[i].y)) { //같은 경우 더 왼쪽인걸 선택한다. 
                        minEnemy[i] = tempEnemy;
                        minDistance[i] = distance;
                    }
                }
                cc++; //한칸 이동
                tempEnemy.x += 1; //한칸 이동시킴
            }

            for (Enemy enemy : minEnemy) { //각 지워저야 할 적의 isDie플래그를 변경한다.
                if (enemy == null) continue;
                enemy.isDie = true;
            }
        }
        maxDie = Math.max(maxDie, dieCnt); //모든 적이 없어진경우 가장 많이 죽은 적의 수로 갱신한다.
    }
}

dalle-mini/dalle-mini