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

오랜만의 포스팅.
그간 정말 많은 일이 있었지만, 정말 인상깊은 문제를 풀어서 기억이 날아가기 전에 얼른 기록하고자 글을 적어본다...

🚨 실력이 뛰어나지 않아 코드가 지저분할 수 있습니다! 🚨

문제

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

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

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

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

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

풀이

• 궁사의 조합을 구하고(m개 중 3개를 뽑는 조합), 각 조합을 모두 게임에 넣어보며 최대로 적을 죽일 수 있는 경우를 구한다.

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

public class Boj17135 {
    /*
     * 각 칸에 포함된 적의 수는 최대 하나
     * n + 1칸에는 성이 있다, 궁수 3명을 배치해야 한다.
     * 각 궁수는 턴마다 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다.
     * 궁수가 공격하는 적은 거리가 d 이하인 적 중에서 가장 가까운 적. 여럿일 경우에는 가장 왼쪽에 있는 적.
     * 같은 적이 여러 궁수에게 공격당할 수 있으며, 공격받으면 게임에서 제외된다.
     * 궁수의 공격이 끝나면 적이 이동한다. 아래로 한 칸 이동하며, 성이 있는 칸으로 이동하면 게임에서 제외
     * 모두 제외되면 게임 끝
     * 궁수의 공격으로 제거할 수 있는 적의 최대 수 계산
     * 거리 계산은 Math.abs(r1 - r2) + Math.abs(c1 - c2)
     */

    static int[] sel;
    static int n, m, d, ans;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken()); // 궁수의 공격거리 제한
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sel = new int[3];
        combination(0, 0);
        System.out.println(ans);
    }

    static void combination(int idx, int cnt) {
        if (cnt == sel.length) {
            // 게임 진행
            // 궁사의 행은 n, 열은 sel[i]

            int[][] archer = new int[3][2];
            for (int i = 0; i < 3; i++) {
                archer[i][0] = n;
                archer[i][1] = sel[i];
            }

            int[][] nowMap = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    nowMap[i][j] = map[i][j];
                }
            }

            game(archer, nowMap);
            return;
        }

        for (int i = idx; i < m; i++) {
            sel[cnt] = i;
            combination(i + 1, cnt + 1);
        }

    }

    static void game(int[][] ac, int[][] nowMap) {
        int enemyCnt = 0;

        while (true) {
            // 궁수의 배치는 -> m 중에 3개 조합 -> ac로 가져옴

            // 매 턴마다 궁수는 적 하나를 공격한다.
            // 아랫즐 왼쪽부터 보면서 값이 1일 경우 거리 비교 후 최솟값 기록 (같은거 x 더 작은거 o)
            // 본 줄에서 적이 있으면 윗줄 볼필요 x 적이 없으면 계속 진행 (~ 거리가 d 이하일때까지)
            Queue<int[]> enemy = new LinkedList<>();

            for (int k = 0; k < 3; k++) {
                int[] nowAc = ac[k];
                int min = Integer.MAX_VALUE;
                int minR = -1, minC = Integer.MIN_VALUE;
                for (int i = n - 1; i >= 0; i--) {
                    for (int j = 0; j < m; j++) {
                        if (nowMap[i][j] == 1) {
                            int dist = Math.abs(nowAc[0] - i) + Math.abs(nowAc[1] - j);
                            if (dist <= d) {
                                if (dist < min) {
                                    min = dist;
                                    minR = i; minC = j;
                                } else if (dist == min) {
                                    if (minC > j) {
                                        minR = i; minC = j;
                                    }
                                    // 현재 열이 minLeft보다 크면 갱신하지 않는다
                                }
                            }
                        }
                    }
                }

                if (minR != -1 && minC != -1) {
                    enemy.add(new int[] {minR, minC});
                }
            }

            while (!enemy.isEmpty()) {
                int[] nowEn = enemy.poll();

                int r = nowEn[0];
                int c = nowEn[1];

                if (nowMap[r][c] == 1) {
                    nowMap[r][c] = 0;
                    enemyCnt++;
                }
            }

            // 한 분기가 지날 때마다 적은 아래로 한 칸 이동
            int sum = 0;
            for (int i = n - 1; i >= 1; i--) {
                for (int j = 0; j < m; j++) {
                    nowMap[i][j] = nowMap[i - 1][j];
                    sum += nowMap[i][j];
                }
            }

            // n+1로 이동할 경우 게임에서 제외
            for (int j = 0; j < m; j++) {
                nowMap[0][j] = 0;
            }

            // 모든 적이 제외되면 게임 끝
            if (sum <= 0) break;
        }

        ans = Math.max(ans, enemyCnt);
    }

}

교수님께서 구현 문제가 코테에서 나오면 가장 마지막에 풀라는 이유를 알 수 있었던 문제였다...
딱 보기에는 금방 구현할 수 있을 것 같으면서도, 은근 까다로워 정~~말 오랜 시간에 걸쳐 풀었다. 3시간은 걸린듯... ^^
명심하자. 구현문제는 맨 마지막에 풀기!
코드가 다소 더럽긴 하지만 그래도 이제는 골드3 문제도 스스로 풀 수 있는 내 자신 칭찬해~! 많이컸다..! 👍