[백준] 17135 - 캐슬 디펜스

난이도 - G3

사용 개념 - 조합 + 브루트포스 + 구현 + BFS

 

핵심 키워드 

 * 1. 같은 거리에 있다면 가장 왼쪽에 있는 적을 처치한다.
 * 2. 여러 명의 궁수가 같은 적을 공격할 수 있다. ----> BFS의 결과 확인을 동일 시간대에  확인해야함. 
 * 3. 좌, 중, 우 순으로 조회

 

 

 

 

- 궁수는 거리가 가까운 적부터 처리한다. 만약 거리가 같은 적이 여럿 존재한다면 가장 왼쪽의 적부터 처리한다.

- 다른 궁수가 같은 타겟을 공격할 수 있다. 즉, 동일 시간대에 처리되는 적에 대한 상황을 생각해야한다.

 

- 1번의 사이클이 끝나고 난다면 적이 1칸 내려온다 ( --> 궁수가 1칸 전진한다와 같은 의미)

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
 
/**
 * @date 2024.02.17
 * @link https://www.acmicpc.net/problem/1987
 * @keyword_solution 
 * 조합 + BFS + 구현 + 브루트포스 
 * 
 * 핵심 
 * 1. 같은 거리에 있다면 가장 왼쪽에 있는 적을 처치한다.
 * 2. 여러 명의 궁수가 같은 적을 공격할 수 있다. ----> BFS의 결과 확인을 동일 시간대에  확인해야함. 
 * 3. 좌, 중, 우 순으로 조회
 * 
 * 순서
 *  1. 조합을 통해 총 3명의 궁수를 0~m-1위 위치에 배치
 *  2. 조합이 완료되면 궁수가 처치할 수있는 적의 최대치 확인 
 *  2-1. 거리 1에서 적을 만나면 BFS 미실시 
 *  2-2. 거리 1에서 적이 없다면,BFS로 최소 거리의 적을 처치 
 *  3. 처치할 수 있는 적의 최대 마리수 파악 후, 궁수의 거리를 1칸 위로 이동 ( == 적들이 1칸 아래로 이동) 
 *  4. 이 과정을 n번 반복
 * 
 * @input (3<= N, M <=15) (1 <= D <= 10)
 * @output 최대 처치할 수 있는 적을 출력
 * @time_complex O(n²)
 * @perf 29776KB 180ms
 */
 
public class Main {
    // 궁수 클래스
    static class Archer {
        int x;
        int y;
 
        public Archer(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public String toString() {
            return "Archer [x=" + x + ", y=" + y + "]";
        }
    }
 
    // 적 클래스
    static class Enemy {
        int x;
        int y;
 
        public Enemy(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public String toString() {
            return "Enemy [x=" + x + ", y=" + y + "]";
        }
 
    }
 
    static int n, m, k, d;
    static StringTokenizer st;
    static int[][] arr;
    static int[] dx = { 0, -1, 0 };
    static int[] dy = { -1, 0, 1 };
    static int max;
    static Archer[] archers;
    static StringBuilder sb;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        archers = new Archer[3];
        max = 0;
        combination(0, 0);
        System.out.println(max);
        br.close();
    }
 
    // 조합
    static void combination(int depth, int start) {
        if (depth == 3) {
            battle();
            return;
        }
        for (int i = start; i < m; i++) {
            archers[depth] = new Archer(n, i);
            combination(depth + 1, i + 1);
        }
    }
 
    static void battle() {
        boolean[][] killCheck = new boolean[n][m];
        Archer[] battleArcher = new Archer[3];
        for (int i = 0; i < 3; i++) {
            battleArcher[i] = archers[i];
        }
        int[][] battleMap = copyArray();
        int cnt = 0;
        for (int loop = 0; loop < n; loop++) {
            for (int i = 0; i < 3; i++) {
                Archer archer = battleArcher[i];
                // 1칸 바로 앞에 적이 있다면 BFS 미실시
                if (battleMap[archer.x - 1][archer.y] == 1) {
                    killCheck[archer.x - 1][archer.y] = true;
                }
                // 바로 앞에 적이 없다면, BFS로 최단 거리 적 탐색
                else {
                    bfs(battleMap, killCheck, new Enemy(archer.x - 1, archer.y));
                }
            }
            // 궁수 한 칸 전진
            for (int i = 0; i < 3; i++) {
                Archer now = new Archer(battleArcher[i].x, battleArcher[i].y);
                now.x -= 1;
                battleArcher[i] = now;
            }
            // 처치 한 적은 0으로 바꿔주기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (killCheck[i][j]) {
                        battleMap[i][j] = 0;
                        killCheck[i][j] = false;
                        cnt++;
                    }
                }
            }
            max = Math.max(max, cnt);
        }
    }
    
    static void bfs(int[][] battleMap, boolean[][] killCheck, Enemy now) {
        Queue<Enemy> q = new ArrayDeque<>();
        q.offer(now);
        boolean[][] visited = new boolean[n][m];
        int startX = now.x + 1;
        int startY = now.y;
        visited[now.x][now.y] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Enemy enemy = q.poll();
                for (int j = 0; j < 3; j++) {
                    int nextX = enemy.x + dx[j];
                    int nextY = enemy.y + dy[j];
                    int distance = Math.abs(startX - nextX) + Math.abs(startY - nextY);
                    if (!rangeCheck(nextX, nextY) || visited[nextX][nextY])
                        continue;
                    if (distance > d)
                        continue;
                    
                    // 최단 거리 적을 찾으면 BFS 즉시 종료 및 배열에서 체크 처리
                    if (battleMap[nextX][nextY] == 1) {
                        killCheck[nextX][nextY] = true;
                        return;
                    } else {
                        q.offer(new Enemy(nextX, nextY));
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
 
    static int[][] copyArray() {
        int[][] copy = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copy[i][j] = arr[i][j];
            }
        }
        return copy;
    }
 
    static boolean rangeCheck(int x, int y) {
        if (x >= 0 && y >= 0 && x < n && y < m)
            return true;
        return false;
    }
}

 

어려웠던 점

- 다른 궁수일지라도 같은 적을 처리할 때의 개념을 생각하지 못했다...

- 조합, 브루트포스, BFS, 구현이 섞여있어 생각보다 어려운 문제였다.