[JAVA] BOJ 백준 17135번 - 캐슬 디펜스

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

나는 각 턴마다 궁수를 죽이는 우선순위를 먼저 구한 후에 풀이를 진행했다. 여기서 턴은 마지막 적이 격자판을 넘어가 사라질 때까지의 과정을 얘기한다. (즉, 0 ~ N-1 차례가 있음)

 

따라서 아래 전역 변수들을 먼저 설명하자면,  N, M, D는 문제에 나와있는 값들을 그대로 대입했고, arr 배열은 각 턴마다 적의 위치를 담은 Tuple 클래스 배열, dieTime 배열은 궁수가 각 턴에 적을 죽일 때 우선순위를 담고 있다.

Tuple 클래스는 적이므로, 각 적들마다 num 멤버 변수를 통해 고유값을 부여하고, far 멤버 변수를 통해 추후에 궁수와 적 사이의 거리를 구해줄 것이다.

static int N;
static int M;
static int D;
static LinkedList<Tuple>[] arr;
static List<Integer>[][] dieTime; // dieTime[x][y] : x가 y시간에 적을 죽일 때 우선순위
static int result;

public static class Tuple implements Comparable<Tuple>{
    int x;
    int y;
    int num;
    int far;

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

    public Tuple(int x, int y, int num, int far) {
        this.x = x;
        this.y = y;
        this.num = num;
        this.far = far;
    }

    @Override
    public int compareTo(Tuple t) {
        if (t.far == this.far) return this.y - t.y;
        return this.far - t.far;
    }
}

 

메인의 solution 함수에서 moveEnemy() 함수를 통해 각 턴의 적들의 위치를 먼저 넣어준다. 그다음에 attackEnemy() 함수를 통해 각 턴마다 각각의 궁수가  적을 죽일 때 우선순위를 구한다.

dieTime[idx][x+1]는 (idx)번의 궁수가 (x+1)턴에 적을 죽이는 우선순위이다. 궁수와 적 사이의 거리가 D값 이하일 경우에만 죽일 수 있는 배열에 담아둔다.

public static void main (String[] args) throws IOException {
    init();
    solution();
    print();
}

public static void solution() {
    result = 0;

    moveEnemy();
    attackEnemy();

    dfs(0, 0, new boolean[M]);
}

public static void moveEnemy() {
    for (int z = 1; z < N; z++) {
        for (Tuple t : arr[z-1]) {
            if (t.x + 1 < N) {
                arr[z].add(new Tuple(t.x + 1, t.y, t.num));
            }
        }
    }
}

public static void attackEnemy() {
    for (int i = 0; i < M; i++) {
        // [N][i]에서 공격했을 때, 각 적들의 dieTime 구하기
        bfs(i);
    }
}

public static void bfs(int idx) {
    for (int x = 0; x < N; x++) {
        PriorityQueue<Tuple> queue = new PriorityQueue<>();

        for (Tuple t : arr[x]) {
            int far = Math.abs(t.x - N) + Math.abs(t.y - idx);

            if (far <= D) queue.add(new Tuple(t.x, t.y, t.num, far));
        }

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            dieTime[idx][x+1].add(tuple.num);
        }
    }
}

 

이제 최대 적을 제거할 수 있는 궁수를 고르기만 남았다.

따라서 solution 함수에서 dfs() 함수를 통해 경우의 수를 구하고 최대 죽일 수 있는 적을 result에 담아둔다.

 

cnt 값이 3이 될 경우, 선택했던 궁수를 getMaxAttack() 함수에 전달해주면서 최대 적을 구한다.

각 턴마다 궁수가 적을 죽이는데, 이미 죽은 적일 경우에는 다음 우선순위인 적을 죽여야 한다.

public static void dfs(int idx, int cnt, boolean[] choice) {
    if (cnt == 3) {
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < choice.length; i++) {
            if (choice[i]) tmp.add(i);
        }

        result = Math.max(result, getMaxAttack(tmp));

        return;
    }
    if (idx == M) return;

    dfs(idx+1, cnt, choice);

    choice[idx] = true;
    dfs(idx+1, cnt+1, choice);
    choice[idx] = false;
}

public static int getMaxAttack(List<Integer> list) {
    int cnt = 0;
    boolean[] isDie = new boolean[arr[0].size()];

    for (int i = 0; i <= N; i++) {
        Set<Integer> tmp = new HashSet<>();

        for (Integer idx : list) {
            for (Integer enemy : dieTime[idx][i]) {
                if (!isDie[enemy]) {
                    tmp.add(enemy);
                    break;
                }
            }
        }

        for (Integer enemy : tmp) {
            cnt++;
            isDie[enemy] = true;
        }
    }

    return cnt;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B17135.java

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

class Main {
    static int N;
    static int M;
    static int D;
    static LinkedList<Tuple>[] arr;
    static List<Integer>[][] dieTime; // dieTime[x][y] : x가 y시간에 적을 죽일 때 우선순위
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        result = 0;

        moveEnemy();
        attackEnemy();

        dfs(0, 0, new boolean[M]);
    }

    public static void dfs(int idx, int cnt, boolean[] choice) {
        if (cnt == 3) {
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < choice.length; i++) {
                if (choice[i]) tmp.add(i);
            }

            result = Math.max(result, getMaxAttack(tmp));

            return;
        }
        if (idx == M) return;

        dfs(idx+1, cnt, choice);

        choice[idx] = true;
        dfs(idx+1, cnt+1, choice);
        choice[idx] = false;
    }

    public static int getMaxAttack(List<Integer> list) {
        int cnt = 0;
        boolean[] isDie = new boolean[arr[0].size()];

        for (int i = 0; i <= N; i++) {
            Set<Integer> tmp = new HashSet<>();

            for (Integer idx : list) {
                for (Integer enemy : dieTime[idx][i]) {
                    if (!isDie[enemy]) {
                        tmp.add(enemy);
                        break;
                    }
                }
            }

            for (Integer enemy : tmp) {
                cnt++;
                isDie[enemy] = true;
            }
        }

        return cnt;
    }

    public static void attackEnemy() {
        for (int i = 0; i < M; i++) {
            // [N][i]에서 공격했을 때, 각 적들의 dieTime 구하기
            bfs(i);
        }
    }

    public static void bfs(int idx) {
        for (int x = 0; x < N; x++) {
            PriorityQueue<Tuple> queue = new PriorityQueue<>();

            for (Tuple t : arr[x]) {
                int far = Math.abs(t.x - N) + Math.abs(t.y - idx);

                if (far <= D) queue.add(new Tuple(t.x, t.y, t.num, far));
            }

            while (!queue.isEmpty()) {
                Tuple tuple = queue.poll();
                dieTime[idx][x+1].add(tuple.num);
            }
        }
    }

    public static class Tuple implements Comparable<Tuple>{
        int x;
        int y;
        int num;
        int far;

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

        public Tuple(int x, int y, int num, int far) {
            this.x = x;
            this.y = y;
            this.num = num;
            this.far = far;
        }

        @Override
        public int compareTo(Tuple t) {
            if (t.far == this.far) return this.y - t.y;
            return this.far - t.far;
        }
    }

    public static void moveEnemy() {
        for (int z = 1; z < N; z++) {
            for (Tuple t : arr[z-1]) {
                if (t.x + 1 < N) {
                    arr[z].add(new Tuple(t.x + 1, t.y, t.num));
                }
            }
        }
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

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

    public static void init() 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());
        arr = new LinkedList[N];
        dieTime = new LinkedList[M][N+1];

        for (int i = 0; i < N; i++) {
            arr[i] = new LinkedList<>();
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j <= N; j++) {
                dieTime[i][j] = new LinkedList<>();
            }
        }

        int cnt = 0;
        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) arr[0].add(new Tuple(i, j, cnt++));
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

꽤 길었던 풀이였던 것 같다. 풀이가 길어질수록 내가 선언했던 변수들에 대한 설정도 잘 기억해야 한 것 같다.

그래서 풀이에서 dieTime[x][y]가 궁수 x가 y턴에 죽일 수 있는 적의 우선순위을 담아두었다고 강조했던 것이었다.ㅎㅎ