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

 

 

 

 

 

 

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

 

문제 출처 : 링크

17135번: 캐슬 디펜스

 

 

최근에 나온 따끈따끈한 문제

이 문제 또한 주어진 제한 조건을 잘 확인하고, 구현으로 옮기면 된다.

 

진행 방식을 요약하면 다음과 같다.

 

1. 궁수 3명을 배치하고 사정거리 안에 있는 가장 가까운 적병을 사격

2. 사격 진행 후 남은 적병들 아래로 한칸 전진

3. 적병이 모두 죽거나, 궁수 칸으로 이동해서 사라질 때까지 1~2번 반복

 

- 주의할 점

1. 만약 궁수에게 가장 가까운 적병이 2개 이상이면, 가장 왼쪽에 위치한 적병을 사격

2. 하나의 적병을 궁수들이 동시에 사격할 수도 있음

 

사격을 통해서 가장 많은 적병을 없앨 수 있는 궁수의 위치에서, 사격한 적병의 수를 출력하면 되는 문제다.

 

 

우선 모든 궁수의 배치 상황을 돌려보며 사격한 최대 적병의 수를 알아내야 한다. 조합을 활용해 궁수를 배치시키고, 필드 위에 모든 적병이 없어질 때까지 while문을 진행한다.

 

최대 열은 15이므로 조합을 진행해도 15C3 = 120으로 시간초과를 걱정할 필요는 없다.

 

* 디펜스 게임 함수 구현 순서

 

1. 전체적인 함수는 하나의 while문으로 진행됨 (탈출조건 : 사전에 체크한 enemy 리스트 사이즈가 0일때) -> 모든 적병들이 다 사격당하거나 궁수한테 왔기 때문이다.

 

2. 2중 포문을 활용해 각 궁수마다 적병간의 최소 이동거리를 알아내고, 사격 영역에 있는 적병을 파악

 

3. 2중 포문이 끝난 이후, 삭제할 적병들을 저장한 리스트를 통한 삭제 과정

 

- 바로 삭제시키지 않고 리스트로 가져와서 삭제하는 이유는, 동시에 사격될 수도 있는 가능성이 있기 때문이다.

- 적병이 사격을 당했을 때만 count 수를 증가시켜준다.

 

4. 남은 적병들 한칸씩 아래로 전진 or 궁수를 한칸씩 위로 전진

5. 전진 이후 궁수칸에 들어간 적병들을 모두 삭제

6. 적병을 저장해둔 리스트의 사이즈가 0이되면 while문 종료. 이때마다 count된 수와 maxCount를 비교하면서 최대 값을 갱신해나가면 끝!

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main_17135_캐슬디펜스_김규석 {
 
    static class Enemy {
        int y;
        int x;
 
        Enemy(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
 
    static int N, M, D;
    static int[][] map;
    static int[][] copy;
    static ArrayList<Enemy> enemy;
    static int arr[];
    static int[] set;
    static int max;
 
    static ArrayList<Enemy> goung;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
 
        map = new int[N + 1][M]; // 궁수 배치를 위해 행 1열 더 만들어줌
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        arr = new int[M];
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        set = new int[3];
        max = Integer.MIN_VALUE;
 
        comb(0, 0);
 
        System.out.println(max);
 
    }
 
    public static void sol(int[][] map) {
 
        int count = 0;
 
        while (enemy.size() != 0) { // 적이 다 사라질 때까지
 
            ArrayList<Enemy> delete = new ArrayList<>();
 
            for (int i = 0; i < goung.size(); i++) {
                int[] dir = new int[enemy.size()];
                int minDir = Integer.MAX_VALUE;
 
                for (int j = 0; j < enemy.size(); j++) { // 거리 저장
                    dir[j] = direction(goung.get(i), enemy.get(j));
                    if (minDir > dir[j])
                        minDir = dir[j];
                }
 
                ArrayList<Enemy> chk = new ArrayList<>();
 
                for (int j = 0; j < enemy.size(); j++) {
                    if (dir[j] == minDir) {
                        if (dir[j] <= D) { // 최소거리면서 사정거리보다 작으면 사격가능한 적
                            chk.add(enemy.get(j));
                        }
                    }
                }
 
                if (chk.size() == 0)
                    continue; // 사격할 적이 없는 상황. continue로 다음으로 넘김
                else if (chk.size() == 1) { // 1개일 경우
                    delete.add(chk.get(0));
                } else if (chk.size() >= 2) { // 2개 이상일 경우
                    int minX = Integer.MAX_VALUE;
 
                    for (int j = 0; j < chk.size(); j++) {
                        if (minX > chk.get(j).x)
                            minX = chk.get(j).x;
                    }
 
                    for (int j = 0; j < chk.size(); j++) {
                        if (chk.get(j).x == minX) {
                            delete.add(chk.get(j));
                        }
                    }
                }
 
            }
 
            // delete에 입력된 적들을 삭제
            for (int i = 0; i < delete.size(); i++) {
                for (int j = 0; j < enemy.size(); j++) {
                    if (delete.get(i).y == enemy.get(j).y && delete.get(i).x == enemy.get(j).x) {
                        enemy.remove(j);
                        count++;
                        break;
                    }
                }
            }
 
            // 한칸씩 땡김
            int c = enemy.size(); // 사이즈 수 저장
            int idx = 0;
            while (c > 0) { // c가 0 이상일때까지 반복
                if(enemy.get(idx).y+1 != N)
                    enemy.add(new Enemy(enemy.get(idx).y + 1, enemy.get(idx).x));
                enemy.remove(idx);
                c--;
            }
            
        }
        
        if(max < count) max = count;
 
    }
 
    public static void comb(int len, int k) {
        if (len == 3) {
            enemy = new ArrayList<>(); // 적을 저장할 리스트 생성
            copy = new int[N + 1][M];
            // map 복사
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    copy[i][j] = map[i][j];
                    if (map[i][j] == 1)
                        enemy.add(new Enemy(i, j));
                }
            }
            goung = new ArrayList<>();
            // 조합을 활용한 궁수 배치
            for (int i = 0; i < 3; i++) {
                copy[N][arr[set[i]]] = 2;
                goung.add(new Enemy(N, set[i]));
            }
            sol(copy);
 
            return;
        }
        if (k == arr.length)
            return;
 
        set[len] = arr[k];
        comb(len + 1, k + 1);
        comb(len, k + 1);
 
    }
 
    public static int direction(Enemy g, Enemy e) {
        return Math.abs(g.y - e.y) + Math.abs(g.x - e.x);
    }
 
}