[백준] 17135번 캐슬 디펜스 (Java)

백준 17135 캐슬 디펜스

DFS를 활용해 조합하고 모든 경우를 확인하는 완전탐색으로 해결했다. 구현하는 과정에서 신경쓸게 많아서 실수도 많았다.

1. 궁수의 위치는 DFS를 활용해 조합한다.
2. 적의 위치는 ArrayList를 이용해 위치를 저장한다.
3. 같은 적을 쏠 수 있기 때문에 바로 적을 제거하는 것이 아니라 target 배열에 저장
4. 적이 내려오는 것은 궁수의 사거리가 1씩 늘리고, 탐색 범위도 1씩 줄였다(성에 들어와도 리스트에서 제거해야 하기 때문)

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

public class Main {

    static int n, m, d;
    static int maxV = 0;
    static ArrayList <int[]> enemyList;
    static int [] comb;
    static void simulate(){
        ArrayList <int[]> tmpEnemyList = new ArrayList<>();
        for(int i = 0; i < enemyList.size(); i ++){
               tmpEnemyList.add(enemyList.get(i));
        }
        int cnt = 0;
        int [] tmp = new int [2];
        int[][]target = new int[3][2];
        for(int p = 0;!tmpEnemyList.isEmpty() && p < n; p++){
            for(int j = 0; j < 3; j ++){
                int minD = 100;
                int [] pos = new int[] {-1, -1};
                for(int i = 0; i < tmpEnemyList.size(); i ++){
                    tmp = tmpEnemyList.get(i);
                    if(tmp[0] >= n - p){
                        tmpEnemyList.remove(tmp);
                        continue;
                    }
                    int tmpD = n - tmp[0] + Math.abs(tmp[1] - comb[j]);
                    if(minD == tmpD && tmp[1] < pos[1]){
                        pos = tmp;
                    } else if(minD > tmpD){
                        minD =tmpD;
                        pos = tmp;
                    }
                }
                if(minD <= d + p) {
                    target[j] = pos;
                } else{
                    target[j]= new int[]{-1, -1};
                }
            }
            for(int [] t : target){
                if (tmpEnemyList.remove(t)) {
                    cnt++;
                }

            }
        }
        maxV = Math.max(maxV, cnt);
    }
    static void dfs(int pos, int cnt){
        if (cnt == 3) {
            simulate();
        } else{
            for(int i = pos; i < m + cnt - 2; i ++){
                comb[cnt] = i;
                dfs(i + 1, cnt + 1);
            }
        }
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st= new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            enemyList = new ArrayList<>();
            comb = new int [3];

            for(int i = 0; i < n; i ++){
                st= new StringTokenizer(br.readLine());
                for(int j = 0; j < m; j ++){
                    if(st.nextToken().equals("1")){
                        enemyList.add(new int [] {i, j});
                    }
                }
            }
            dfs(0, 0);
            System.out.println(maxV);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}