[백준] 17135번 : 캐슬 디펜스 Gold3(골드3) - JAVA[자바]

[Gold III] 캐슬 디펜스 - 17135

문제 링크

성능 요약

메모리: 41344 KB, 시간: 220 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 2월 11일 17:00:14

문제 설명

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

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

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

격자판의 두 위치 (r₁, c₁), (r₂, c₂)의 거리는 |r₁-r₂| + |c₁-c₂|이다.

입력

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

출력

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

 

접근 방법

1. N+1 위치에 아처 3명을 배치 시킨다는 것은 0 ~ M-1 위치 중 3곳을 뽑는 것이다. ( 조합 )

2. 거리가 D이하인 적을 찾으면서 가장 왼쪽인 적을 찾아준 뒤 -1로 갱신해준다. ( 같은 적을 공격할 수 있기 때문에)

3. 궁수들의 공격이 끝나면(턴을 마친다면) 적을 한칸씩 내리는 것이 아닌 아처의 위치를 한칸씩 위로 올려준다.

-> 아처를 기준으로 위 부분만 확인하고 적을 제거해주면 된다.

 4. 만약 결과값이 N * 3(아처가 매턴 잡을 수 있는 적)이라면 출력 후 바로 종료한다.

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

public class Main {
    static int N, M, D, result;
    static int[][] map;
    static int[][] copyMap;
    static int[] archer = new int[3];

    // 상,좌,우
    static int[] dirX = {-1, 0, 0};
    static int[] dirY = {0, -1, 1};

    public static void main(String[] args) throws IOException {
        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());
        copyMap = new int[N][M];
        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());
            }
        }

        combination(0, 0);

        System.out.println(result);
    }

    // 아처가 위치할 수 있는 조합을 얻는 메서드
    private static void combination(int depth, int at) {
        // 조합을 다 찾았다면 copyMap을 복사 후 적을 제거하는 메서드 실행
        if (depth == 3) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    copyMap[i][j] = map[i][j];
                }
            }

            // 적 제거
            removeEnemy();

            // result가 N * 3이라면 그게 최대값이기 때문에 종료
            if(result == N * 3){
                System.out.println(result);
                System.exit(0);
            }
            return;
        }

        // at를 기점으로 출력 후 다음 위치 선정
        for (int i = at; i < M; i++) {
            archer[depth] = i;
            combination(depth + 1, i + 1);
        }
    }

    // 적을 제거하는 메서드
    private static void removeEnemy() {
        int turn = 0; // 현재 몇턴인지 나타내는 변수
        int count = 0; // 제거한 적의 수를 나타내는 변수

        // 나가는 종료: 적이 존재하지 않을 때 , N만큼 턴을 진행했을 때
        boolean exit = false;
        while (turn != N && !exit) {

            // 아처가 N - turn을 통해서 한칸씩 올라감 -> 적이 한칸씩 내려오는 것과 같음
            for (int i = 0; i < 3; i++) {
                bfs(N - turn, archer[i]);
            }

            // 맵에 적이 존재하지 않는다면 종료
            exit = true;
            for (int i = N - turn - 1; i >= 0; i--) {
                for (int j = 0; j < M; j++) {
                    // 사라진 적을 제거 해줌
                    if (copyMap[i][j] == -1) {
                        copyMap[i][j] = 0;
                        count++;
                    }
                    // 적이 존재한다면 exit는 false로 만듬
                    else if (copyMap[i][j] != 0) {
                        exit = false;
                    }
                }
            }

            // 한턴 마칠 때마다 값 증가
            turn++;
        }

        // result 값이 최대값이라면 갱신
        if (result < count) result = count;
    }

    // 아처를 기점으로 가장 가깝거나 가까우면서 가장 왼쪽인 적 찾기
    private static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();

        // 아처의 시작점,거리 삽입
        queue.add(new int[]{x, y, 0});

        // 방문 배열
        boolean[][] visit = new boolean[N][M];

        // 가장 가까운 값을 찾기위해서 MAX_VALUE 미리 삽입
        int minDist = Integer.MAX_VALUE;
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int cur[] = queue.poll();

            // 상,좌,우만 확인하면 된다. -> 밑은 확인 할 필요 X
            for (int i = 0; i < 3; i++) {
                int nX = cur[0] + dirX[i]; // 다음 X
                int nY = cur[1] + dirY[i]; // 다음 Y
                int nextDist = cur[2] + 1; // 아처와의 거리

                // 배열 범위 밖이거나 || 제한 거리 이상이거나 || 방문했다면 continue
                if (nX < 0 || nX >= x || nY < 0 || nY >= M || nextDist > D || visit[nX][nY]) {
                    continue;
                }

                // 다음 위치 방문 처리 후 큐에 삽입
                visit[nX][nY] = true;
                queue.add(new int[]{nX, nY, nextDist});

                // 적이 있다면
                if (copyMap[nX][nY] != 0) {
                    // 최소거리라면 갱신
                    if (nextDist < minDist) {
                        minX = nX;
                        minY = nY;
                        minDist = nextDist;
                    }
                    // 만약 거리가 같다면 Y가 더 작은 값(더 왼쪽인 값)
                    else if (nextDist == minDist) {
                        if (nY < minY) {
                            minX = nX;
                            minY = nY;
                        }
                    }
                }
            }
        }

        // minX 혹은 minY가 최대값이라면 제거 할 적이 없는 것
        if (minX == Integer.MAX_VALUE || minY == Integer.MAX_VALUE) {
            return;
        }

        copyMap[minX][minY] = -1;
    }
}