백준 - 17135번(캐슬 디펜스)

문제 출처: https://www.acmicpc.net/problem/17135

문제

• 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

• 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

• 게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

• 격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int N, M, D, enemyCnt, res;
    private static int[][] map, directions = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };  // 왼쪽 우선

    private static class Node {

        int y;          // 행
        int x;          // 열
        int distance;   // 거리

        public Node(int y, int x, int distance) {
            this.y = y;
            this.x = x;
            this.distance = distance;
        }

    }

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(tokenizer.nextToken());    // 행
        M = Integer.parseInt(tokenizer.nextToken());    // 열
        D = Integer.parseInt(tokenizer.nextToken());    // 궁수의 공격 거리 제한

        map = new int[N + 1][M];                    // 성의 위치까지 고려하여 행을 +1 해준다.
        for (int i = 0; i < N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(tokenizer.nextToken());
                if (map[i][j] == 1) enemyCnt++;
            }
        }

        combination(new int[3], 0, 0);

        System.out.println(res);
    }

    private static void combination(int[] target, int start, int cnt) {
        if (cnt == 3) {
            int removeCnt = 0;
            int totalCnt = enemyCnt;

            int[][] arr = new int[N + 1][M];

            for (int i = 0; i <= N; i++) {
                arr[i] = map[i].clone();
            }

            while (totalCnt != 0) {
                List<Node> removeList = new ArrayList<>();

                // 궁수 3명 배치
                // 가장 가까운 적 찾기(단, 궁수들이 같은 적을 타겟으로 삼을 수도 있음)
                // bfs
                for (int i = 0; i < 3; i++) {
                    Node temp;
                    if ((temp = bfs(new Node(N, target[i], 0), arr)) != null) {
                        // 적을 잡은 경우
                        removeList.add(temp);
                    }
                }

                // 적 제거 처리
                for (Node node : removeList) {
                    if (arr[node.y][node.x] == 1) {
                        arr[node.y][node.x] = 0;
                        removeCnt++;
                        totalCnt--;
                    }
                }

                // 적들의 진격
                int[][] temp = new int[N + 1][M];
                for (int i = 1; i < N; i++) {
                    temp[i] = arr[i - 1].clone();
                }

                int sum = 0;

                for (int i = 0; i < M; i++) {
                    sum += arr[N - 1][i];
                }

                totalCnt -= sum;

                arr = temp;
            }

            res = Math.max(res, removeCnt);

            return;
        }

        for (int i = start; i < M; i++) {
            target[cnt] = i;
            combination(target, i + 1, cnt + 1);
        }
    }

    private static Node bfs(Node start, int[][] arr) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(start);

        boolean[][] visited = new boolean[N + 1][M];

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            int y = curr.y;
            int x = curr.x;
            int dist = curr.distance;

            if (visited[y][x]) continue;
            if (dist <= D && arr[y][x] == 1) return curr;
            if (dist > D) return null;

            visited[y][x] = true;

            for (int i = 0; i < 4; i++) {
                int dy = y + directions[i][0];
                int dx = x + directions[i][1];

                if (dy >= 0 && dy < N && dx >= 0 && dx < M) {
                    if (!visited[dy][dx]) {
                        queue.offer(new Node(dy, dx, dist + 1));
                    }
                }
            }
        }

        return null;
    }

}

• 조합 + BFS를 통해 해결한 문제이다.
• 처음에 문제 이해에서 시간이 오래걸려 푸는데 시간이 조금 걸렸다.
• 입력으로 들어오는 배열 밑에 행에 성이 위치하고, 이 자리에 궁수가 배치될 수 있으므로 입력값의 N에 +1한 크기로 배열을 선언하였다.
• 조합을 통해 궁수를 배치할 인덱스를 고르고, BFS를 통해 각각 궁수들 중 가장 가까운 적들을 찾는다.
• 이때, 공격 거리 내에 있어야하며, 왼쪽이 우선된다.
• BFS를 수행하여 가장 우선순위가 높은 적을 발견하면 Node 객체를 반환하고, 아닐 경우 null을 반환하도록 bfs() 메서드를 작성하였다.
• 3명의 궁수가 같은 적을 조준할 수도 있으므로, 모든 궁수들의 적 스캔 결과를 리스트에 저장해두고 중복이 없도록 처리하였다.
• 적을 처리할 때마다 처리 횟수를 늘리고, 전체 적의 수를 감소시켰다.
• 적을 처리하면 한 턴이 끝나므로 배열 복사를 통해 적들이 한칸씩 내려오는 과정을 구현하였다.
• 이 때, 가장 마지막 행(N-1번 행)에 있던 적들의 수를 계산하여 전체 적의 수에서 빼주었다.
• 이러한 과정이 전체 적들의 수가 0이 될 때까지 반복되고, 조합을 통해 최댓값을 구하도록 하였다.