[백준]17135: 캐슬 디펜스

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|이다.

입력

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

출력

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

제한

• 3 ≤ N, M ≤ 15
• 1 ≤ D ≤ 10

예제 입력 1

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

예제 출력 1

3

---

구현 문제이다. 구현 문제는 꼼꼼하게 분석하는 것이 가장 중요하다고 생각한다. 문제를 잘 읽어보며 내가 구현해야하는 것과 주의해야하는 것을 나열해보았다.

1. 궁수는 총 3명, 성에 겹치지 않게 배치한다.

2. 성은 N+1의 행에 존재한다.
3. 궁수의 사정거리는 D = |r2-r1| + |c2-c1|;
4. 1은 적의 위치이다.
5. 선 공격 후 이동이다.

6. 궁수는 모두 동시에 공격하며 거리가 가까운적이 여럿인 경우 가장 왼쪽에있는 적을 공격한다.

7. 적은 아래로만 이동하며, 성에 도착하면 사라진다.

문제에 적용하고 구현하는 리스트는 다음과 같다.

나는 이러한 조건을 보고 다음과 같이 구상해야겠다고 생각했다.

1) 궁수를 배치한다.

2) 각 궁수별로 잡아야하는 적을 찾는다.

3) 동시에 죽인다.

4) 적을 움직인다.

1~4를 조건에 맞게 잘 구현만 하면 될 것 같다. 코드를 하나하나 보여주며 설명해보면 더 쉽게 이해될 것 같다.

 

1. 궁수를 배치한다.

우리는 총 M칸(M>=3)에 3명의 궁수를 배치해야한다. 여기서 우린 N개중 3개를 뽑는 조합을 생각할 수 있다. 순열이 아닌 이유는 1, 2, 3 과 1, 3, 2를 다르게 볼 이유가 없기 때문이다.

따라서 나는 placeArcher라는 함수명으로 조합을 구현하였다.

placeArcher(0, 1, new int[M], map);

private static void placeArcher(int start, int cnt, int[] archerPos, int[][] map) {
    if(cnt == 4) {
        int[][] tmpMap = new int[N][M];
        //깊은 복사
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                tmpMap[i][j] = map[i][j];
            }
        }
        
        //구현 시작
        int killCnt = 0;
        for(int i=0; i<N; i++) {
            killCnt += killEnemy(archerPos, tmpMap);
            moveEnemy(tmpMap);
        }
        max = Math.max(killCnt, max);
        return;
    }
    for(int i=start; i<M; i++) {
        archerPos[i] = cnt;
        placeArcher(i+1, cnt+1, archerPos, map);
        archerPos[i] = 0;
    }
}

archerPos라는 배열은 크기 M으로 모두 0으로 초기화 돼 있고, 총 3명을 뽑게되면(1부터 시작해 4에 종료되므로 3명이 뽑힌다.) 뽑힌 자리에 1, 2, 3이 각각 들어가게된다.

이후에 궁수를 배치할때마다 몇명을 잡을 수 있는지 확인해야해 원본 map이 변하지 않게 tmpMap에 깊은 복사를 해주었다. 이후에 구현을 시작하게된다.

구현 순서는 위의 2, 3, 4를 총 N번 반복하게된다.

2. 적을 죽인다.

적을 죽이는것은 적 위치 탐색 > 적 죽이기 순으로 이루어진다.

private static int killEnemy(int[] archerPos, int[][] map) {
    // 궁수 3명이 죽여야하는 적의 x좌표, y좌표, 거리를 반환해서 넣어주려는 함수
    int[][]killPos = new int[3][3];
    int j=0;
    int kCnt = 0;
    for(int i=0; i<M; i++) {
        if(archerPos[i]==0) continue;
        killPos[j] = getCloseEnemy(N, i, map);
        j++;
    }

    for(int i=0; i<3; i++) {
        if(killPos[i][2] <= D) {
            int dx = killPos[i][0];
            int dy = killPos[i][1];
            if(dx == -1 || map[dx][dy]==0) continue;
            map[dx][dy] = 0;
            kCnt++;
        }
    }
    return kCnt;
}

dx=-1은 잡을 수 있는 적이 없는 경우이고, map=0은 현재 적이 아닌 경우이므로 skip이 가능하다.

private static int[] getCloseEnemy(int x, int y, int[][] map) {
    int min = Integer.MAX_VALUE;
    int ex = -1;
    int ey = -1;
    for(int j = 0; j<M; j++) {
        for(int i=N-1; i>=0; i--) {
            if(map[i][j] == 0) continue;
            int dist = Math.abs(x-i) + Math.abs(y-j);
            if(dist > D) continue;
            if(min > dist) {
                min = dist;
                ex = i;
                ey = j;
            }
        }
    }
    return new int[]{ex, ey, min};
}

문제 조건에서 반드시 왼쪽에있는 적부터 잡아야한다는 조건을 만족하기위해 ↑↑ 방식으로 탐색을 진행한 모습이다.

3. 적 움직이기

이번 문제에서 가장 간단한 구현이다. 모든 적을 한칸 아래로 내려주면된다.

private static void moveEnemy(int[][] map) {
    for(int i=N-1; i>0; i--) {
        for(int j=0; j<M; j++) {
            map[i][j] = map[i-1][j];
        }
    }
    for(int j=0; j<M; j++) {
        map[0][j] = 0;
    }
}

구현을 마친 후 최댓값을 출력해주면 문제가 끝이난다.

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_G4_17135_캐슬디펜스 {
    static int N, M, D;
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws Exception {
        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());
        int[][] 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());
            }
        }

        placeArcher(0, 1, new int[M], map);
        System.out.println(max);
    }

    private static void placeArcher(int start, int cnt, int[] archerPos, int[][] map) {
        if(cnt == 4) {
            int[][] tmpMap = new int[N][M];
            //깊은 복사
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    tmpMap[i][j] = map[i][j];
                }
            }

            //구현 시작
            int killCnt = 0;
            for(int i=0; i<N; i++) {
                killCnt += killEnemy(archerPos, tmpMap);
                moveEnemy(tmpMap);
            }
            max = Math.max(killCnt, max);
            return;
        }
        for(int i=start; i<M; i++) {
            archerPos[i] = cnt;
            placeArcher(i+1, cnt+1, archerPos, map);
            archerPos[i] = 0;
        }
    }

    private static int killEnemy(int[] archerPos, int[][] map) {
        // 궁수 3명이 죽여야하는 적의 x좌표, y좌표, 거리를 반환해서 넣어주려는 함수
        int[][]killPos = new int[3][3];
        int j=0;
        int kCnt = 0;
        for(int i=0; i<M; i++) {
            if(archerPos[i]==0) continue;
            killPos[j] = getCloseEnemy(N, i, map);
            j++;
        }

        for(int i=0; i<3; i++) {
            if(killPos[i][2] <= D) {
                int dx = killPos[i][0];
                int dy = killPos[i][1];
                if(dx == -1 || map[dx][dy]==0) continue;
                map[dx][dy] = 0;
                kCnt++;
            }
        }
        return kCnt;
    }

    private static int[] getCloseEnemy(int x, int y, int[][] map) {
        int min = Integer.MAX_VALUE;
        int ex = -1;
        int ey = -1;
        for(int j = 0; j<M; j++) {
            for(int i=N-1; i>=0; i--) {
                if(map[i][j] == 0) continue;
                int dist = Math.abs(x-i) + Math.abs(y-j);
                if(dist > D) continue;
                if(min > dist) {
                    min = dist;
                    ex = i;
                    ey = j;
                }
            }
        }
        return new int[]{ex, ey, min};
    }

    private static void moveEnemy(int[][] map) {
        for(int i=N-1; i>0; i--) {
            for(int j=0; j<M; j++) {
                map[i][j] = map[i-1][j];
            }
        }
        for(int j=0; j<M; j++) {
            map[0][j] = 0;
        }
    }
}