[BOJ] 백준 17135번 : 캐슬 디펜스 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

문제

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

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

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

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

 

풀이

조합과 브루트포스를 이용한 시뮬레이션 문제였습니다. 궁수를 배정하는 것 자체는 조합으로 어렵지 않게 구현할 수 있었고, 적을 공격하는 함수는 브루트포스를 활용하여 구현할 수 있었습니다.

다만, 적을 공격할 때 주의할 점이 2가지 있었습니다.

1. 여러 명의 궁수가 같은 적을 공격할 수도 있다.

2. 적의 최단 거리가 같을 경우, 왼쪽 적부터 공격한다.

1번 사항에 경우, 저는 visited라는 boolean 타입 배열을 만들어서 해결하였습니다. 궁수가 최단거리의 적을 발견하자마자 바로 적을 제거하는 것이 아니라, visited[i][j] = true 처리한 뒤, 궁수의 공격이 모두 끝나면 visited 배열에서 true인 좌표의 개수를 셌습니다.

2번 사항에 경우, 최단 거리를 계속해서 초기화나가되, 과거에 구해 둔 거리와 현재 새롭게 구한 거리가 같을 경우, 그 두 거리의 x좌표를 비교하였습니다. 즉, 최단 거리가 같을 경우 x좌표가 작은 쪽의 거리로 초기화하는 것입니다.

 

위 사항을 고려한 저의 로직은 아래와 같습니다.

1. 조합을 이용하여 궁수의 x좌표를 뽑아냄.

2. 각 궁수에 대하여 전체 맵에서 적이 존재하는 좌표를 구한 뒤, 거리를 구함.

3. 2번 과정에서 최단거리, 최단거리가 가리키는 x, y좌표를 구함.

4. 3번 과정에서 구한 x, y좌표를 visited[x][y] = true 처리함.

5. visited에서 true인 부분만 개수를 셈

6. i번째 배열을 i-1번째 배열로 초기화 함. (위에서 아래로)

7. 1~6번 과정을 N번만큼 반복했으면 종료한다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, D;
    static int[][] map;
    static int[][] copyMap;
    static int ans;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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 + 1][M + 1];
        copyMap = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                copyMap[i][j] = map[i][j];
            }
        }
 
        ArrayList<Integer> archer = new ArrayList<>();
        ans = 0;
        comb(1, M, 3, archer);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // map을 원래대로 변경.
    public static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = copyMap[i][j];
            }
        }
    }
 
    // 거리
    public static int distance(int r1, int r2, int c1, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2);
    }
 
    // 조합
    public static void comb(int start, int n, int r, ArrayList<Integer> archer) {
        if (r == 0) {
            init();
            attack(archer);
            return;
        }
 
        for (int i = start; i <= n; i++) {
            archer.add(i);
            comb(i + 1, n, r - 1, archer);
            archer.remove(archer.size() - 1);
        }
    }
 
    // 궁수가 적을 공격하는 함수.
    public static void attack(ArrayList<Integer> archer) {
        int res = 0;
 
        // 최대 N턴까지 진행할 수 있음.
        for (int n = 1; n <= N; n++) {
            boolean[][] visited = new boolean[N + 1][M + 1];
            for (int k = 0; k < archer.size(); k++) {
                int temp = archer.get(k); // 궁수가 서 있는 x좌표
                int minD = Integer.MAX_VALUE; // 최소 거리
                int minR = Integer.MAX_VALUE; // 최소 거리의 y좌표
                int minC = Integer.MAX_VALUE; // 최소 거리의 x좌표
 
                // 맵 전체를 탐색해서 최단거리를 찾아내는 것이 목적.
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= M; j++) {
                        if (map[i][j] == 1) { // 적이 있을 경우
                            if (minD >= distance(i, N + 1, j, temp)) {
                                // 현재 구한 최소 거리보다 더 짧은 거리가 발생할 경우
                                // 최단거리와 좌표들을 다시 초기화.
                                if (minD > distance(i, N + 1, j, temp)) {
                                    minD = distance(i, N + 1, j, temp);
                                    minR = i;
                                    minC = j;
                                } else {
                                    // 현재 구한 최소 거리와 지금 구한 최소 거리가 같을 경우,
                                    // 가장 왼쪽 적부터 처지해야하므로 x좌표가 더 작은지 검사해야 함.
                                    if (minC > j) {
                                        minR = i;
                                        minC = j;
                                    }
                                }
                            }
                        }
                    }
                }
 
                // 위에 과정을 모두 거친 후, 최소 거리가 D보다 작으면,
                // 그 좌표에 visited 처리를 해 준다.
                if (minD <= D) {
                    visited[minR][minC] = true;
                }
            }
 
            // visited가 true인 좌표만 적을 처지한다.
            // 궁수가 같은 적을 쏠 수도 있기때문에 바로 바로 map[i][j] = 0하면 안 된다.
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (visited[i][j]) {
                        map[i][j] = 0;
                        res++;
                    }
                }
            }
 
            // 성 바로 위 줄을 모두 0으로 초기화.
            for (int i = 1; i <= M; i++) {
                map[N][i] = 0;
            }
 
            // i번째 줄을 i-1번째 줄로 초기화.
            for (int i = N; i >= 1; i--) {
                for (int j = 1; j <= M; j++) {
                    map[i][j] = map[i - 1][j];
                }
            }
        }
 
        ans = Math.max(ans, res);
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.