[ 백준 / BOJ 17135 ] 캐슬 디펜스 ( 자바 / JAVA )

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

17135번: 캐슬 디펜스

문제 설명

캐슬 디펜스 👉 성을 향해 몰려오는 적을 잡는 턴 방식 게임

NxM 크기의 격자판에서 진행
N번행 바로 아래(N+1번 행)의 모든 열에 성이 존재

궁수
👉 3명 존재
👉 각 턴마다 적 하나를 공격 가능, 모든 궁수는 동시 공격
👉 거리가 D이하인 적 중 가장 가까운 적

• 여럿일 경우, 가장 왼쪽에 있는 적 공격
• ($r_1$,$c_1$), ($r_2$,$c_2$)의 거리 = |$r_1$-$r_2$| + |$c_1$-$c_2$|

턴이 끝나면 적은 아래로 한 칸 이동, N+1행이 되면 게임에서 제외 👉 모든 적이 제외되면 종료
제거할수 있는 적의 최대 수 출력

 

문제 풀이

1. 3명의 궁수를 배치할 위치 선택

selArchers(cnt, idx, combiOfArcher)
cnt : 선택된 궁수의 수
idx : 선택된 열 값의 다음 값
combiOfArcher : 3명의 선택된 궁수의 열 값 배열

for문을 돌면서 combiOfArcher에 0~N-1 중 3개의 조합을 선택

세 위치가 모두 선택되면 공격~!!

2. 공격 && kill 수

attack(combiOfArcher)

원래는 한 턴이 끝나면 적이 앞으로 이동하지만, 궁수의 행을 옮기는 것이 더 간단하여 그것으로 구현

turn의 값이 N보다 작을 동안 반복

궁수의 행 위치 : x = N - turn
궁수의 열 위치 : y = combiOfArcher[k]

공격가능한 적을 탐색
👉 D이하 거리 중, 가장 가깝고 왼쪽인 적의 위치를 q에 new int[]{minX, minY} 저장

모두 탐색하면, 공격 killOfTurn += 1;

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BOJ_17135_캐슬_디펜스 {
    static int N, M, D, ans = Integer.MIN_VALUE;
    static int[][] enemyOfMap, copyOfMap;
    static int[] archer;

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

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

        enemyOfMap = new int[N][M];
        copyOfMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                enemyOfMap[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

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

        int[] combiOfArcher = new int[3];
        selArchers(0, 0, combiOfArcher);

        System.out.println(ans);
    }

    private static void selArchers(int cnt, int idx, int[] combiOfArcher) {
        if (cnt == 3) {
            ans = ans < attack(combiOfArcher) ? attack(combiOfArcher) : ans;
            return;
        }
        for (int i = idx; i < archer.length; i++) {
            combiOfArcher[cnt] = archer[i];
            selArchers(cnt + 1, idx + 1, combiOfArcher);
        }
    }

    private static int attack(int[] combiOfArcher) {
        for(int i = 0 ; i < N ; i++)
            copyOfMap[i] = Arrays.copyOf(enemyOfMap[i], M);

        int killOfTurn = 0;
        int turn = 0;
        Queue<int[]> q = new LinkedList<>();

        while (turn < N) {
            for (int k = 0; k < 3; k++) {
                int x = N - turn;
                int y = combiOfArcher[k];

                int min = Integer.MAX_VALUE;
                int minX = -1;
                int minY = -1;

                for (int i = N - turn - 1; i >= 0; i--) {
                    for (int j = 0; j < M; j++) {
                        if (copyOfMap[i][j] == 1) {
                            int dist = Math.abs(i - x) + Math.abs(j - y);

                            if(dist > D) continue;

//                            System.out.println("M : " + M + " dist: " + dist);
                            if (dist < min) {
                                min = dist;
                                minX = i;
                                minY = j;
                            } else if (dist == min) {
                                if (j < minY) {
                                    minX = i;
                                    minY = j;
                                }
                            }
                        }
                    }
                }

                if(minX == -1 || minY == -1) continue;

                q.offer(new int[]{minX, minY});
//                System.out.println("turn : " + turn + " x : " + minX + " y : " + minY + " dist : " + min);
            }

            while (!q.isEmpty()) {
                int x = q.peek()[0];
                int y = q.poll()[1];

                if(copyOfMap[x][y] == 1){
                    copyOfMap[x][y] = 0;
                    killOfTurn += 1;
                }
//                System.out.println("turn : " + turn + " x : " + x + " y : " + y + " kill : " + killOfTurn);
            }
            turn += 1;
        }
        return killOfTurn;
    }
}