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

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

17135번: 캐슬 디펜스

조합과 완전탐색을 사용하여 풀 수 있다.

 

핵심

궁수는 N+1위 치에 3명 배치할 수 있다. 1 턴에 1명을 맞출 수 있고, 다른 궁수도 같은 적을 맞 출 수 있다.

궁수의 위치를 바꾸어가며 그때마다 잡은 적의 수를 카운트해야 한다.

 

 

정답 코드

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

public class Main {
    static int N;
    static int M;
    static int D;
    static int answer = 0;
    static int[][] map;
    static int[][] originMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] info = br.readLine().split(" ");
        N = Integer.parseInt(info[0]);
        M = Integer.parseInt(info[1]);
        D = Integer.parseInt(info[2]);
        map = new int[N + 1][M + 1];
        originMap = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            String[] mapInfo = br.readLine().split(" ");
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(mapInfo[j-1]);
                originMap[i][j] = map[i][j];
            }
        }
        int[] archer = new int[3];
        setArcher(1, 0, archer);
        System.out.println(answer);
    }

    public static void setArcher(int start, int settingCount, int[] archer) {
        if (settingCount == 3) {
            init();
            attack(archer);
            return;
        }
        for (int i = start; i <= M; i++) {
            archer[settingCount] = i;
            setArcher(start + 1, settingCount + 1, archer);
        }
    }

    public static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = originMap[i][j];
            }
        }
    }

    public static int distance(int x1, int x2, int y1, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public static void attack(int[] archer) {
        int count = 0;
        for (int n = 1; n <= N; n++) {
            boolean[][] visited = new boolean[N + 1][M + 1];
            for (int i = 0; i < 3; i++) {
                int archerX = archer[i];
                int minD = Integer.MAX_VALUE;
                int minX = Integer.MAX_VALUE;
                int minY = Integer.MAX_VALUE;

                for (int j = 1; j <= N; j++) {
                    for (int k = 1; k <= M; k++) {
                        if (map[j][k] == 1) {
                            int distance = distance(k, archerX, j, N + 1);
                            if (distance < minD) {
                                minD = distance;
                                minX = k;
                                minY = j;
                            } else if (distance == minD) {
                                if (k < minX) {
                                    minX = k;
                                    minY = j;
                                }
                            }
                        }
                    }
                }
                if (minD <= D) {
                    visited[minY][minX] = true;
                }
            }
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (visited[i][j]) {
                        map[i][j] = 0;
                        count++;
                    }
                }
            }
            for (int i = N; i >= 1; i--) {
                for (int j = 1; j <= M; j++) {
                    map[i][j] = map[i - 1][j];
                }
            }
        }
        answer = Math.max(count, answer);
    }
}

해설

우선 각 궁수의 배치마다 새로운 게임을 시작해야 하기 때문에 orginMap을 선언하여 init() 메서드 호출마다 초기화시킨다.

이제 조합을 사용하여 궁수를 3명 순서대로 배치하고 배치가 완료되었다면, 맵을 초기화하고 게임을 시작한다.

총 N번 실행되는데 이유는 맵이 1칸씩 당겨지므로 최대 N번 실행해야 한다.

이제 궁수의 위치별로 가장 가까운 적을 visited로 체크한다.

여기서 count를 바로 올리지 않고, visited를 사용한 이유는 궁수가 같은 적을 공격하는 경우가 있기 때문이다.

3명의 궁수가 공격이 끝났다면 맵을 1칸 당긴다.

이를 N번 반복 후 최대 값을 구한다.