백준 17155 캐슬 디펜스 (Java)

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

 

1. 문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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

2. 풀이

궁수의 위치는 map의 가장 아래 한 줄에서 세 자리를 뽑아 선별할 수 있다. 최대 map 크기(15*15)라 가정했을 때 

궁수의 위치는 가장 아래의 15칸에서 3개를 뽑는 경우이다. 즉 m칸의 map이 주어졌을 때 시간복잡도는 O(mC3), 브루트포스로 해결할 수 있다.

 

해당 문제의 과정은 다음과 같이 쪼개어 생각할 수 있다.

1. m칸의 자리 중 세 칸을 골라 궁수를 배치한다.
2. 선정한 위치에서 게임을 진행한다
   1. 각 궁수에 대해 가장 가까운 적 중 왼쪽에 위치한 적을 탐색한다.
   2. 해당 적들을 사살하고, 그 수를 센다.
   3. 모든 적들을 아래로 한 칸 이동시킨다.
   4. 모든 적을 제거할 때까지 2-1~2-3을 반복한다.
3. 모든 자리의 궁수에 대해 계산을 할 때까지 반복한다.

2-1. 궁수의 자리 배치

    private static void combine(int m, int cnt, boolean[] archer) {

        //적 사냥 수행
        if (cnt == 3) {
            hunt(archer);
            return;
        }

        //궁수의 위치 선정
        for (int i = 0; i < m; i++) {

            if (!archer[i]) {
                archer[i] = true;
                combine(m, cnt + 1, archer);
                archer[i] = false;
            }
        }

    }

백트래킹으로 구현한다. m칸에 대해 각 칸에 궁수가 존재하지 않을 경우, 궁수를 배치한다.

2-2. 게임을 진행한다.

2-2-1. 각 궁수에 대해 가장 가까운 적 중 왼쪽에 위치한 적을 탐색한다.

        //적 처치 횟수
        int cnt = 0;

        while (true) {

            //각 궁수에 대해 bfs를 돌려서 처리할 적 선택
            List<Node> kill = new ArrayList<>();

            for (Integer ar : arc) {

                boolean[][] visit = new boolean[n + 1][m];

                Queue<Node> qu = new ArrayDeque<>();

                qu.offer(new Node(n, ar, 0));
                visit[n][ar] = true;
                int killy = 987654321;
                int killx = 987654321;
                int killcnt = 987654321;

                while (!qu.isEmpty()) {

                    Node cur = qu.poll();

                    //적을 만난 시점에서 더 진행해봐야 거리가 멀어지므로 조건에 부합하지 않게 됨 -> bfs stop
                    if (map2[cur.y][cur.x] == 1) {
                        if (cur.cnt < killcnt) {
                            killy = cur.y;
                            killx = cur.x;
                            killcnt = cur.cnt;
                        } else if (cur.cnt == killcnt && cur.x < killx) {
                            killy = cur.y;
                            killx = cur.x;
                            killcnt = cur.cnt;
                        }

                        continue;
                    }

                    //궁수와의 거리가 d -> 더 이상 늘어날 수 없음
                    if (cur.cnt == d) {

                        continue;
                    }


                    //상하좌우에 대해 bfs 방문
                    for (int i = 0; i < 4; i++) {
                        int ny = cur.y + dy[i];
                        int nx = cur.x + dx[i];

                        //map 범위 확인
                        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

                        if (!visit[ny][nx]) {
                            visit[ny][nx] = true;
                            qu.offer(new Node(ny, nx, cur.cnt + 1));
                        }
                    }

                }

                //거리의 갱신 -> 사거리 내에 적이 존재함
                if (killcnt != 987654321) {
                    kill.add(new Node(killy, killx, killcnt));
                }

            }

arc 리스트에는 궁수의 칸 수가 들어있다. 각 궁수에 대해 BFS를 수행한다. 거리는 문제에 의해 (가로 길이)+(세로 길이)이므로 새로운 노드를 방문할 때 weight는 1씩 증가한다. 

탐색하다 적을 만났다면 해당 위치에서는 더 이상 탐색이 의미가 없으므로 궁수로부터의 거리와 왼쪽의 치우침 여부를 계산하여 갱신해준다. 궁수의 사거리 끝에 도달했을 경우에도 탐색을 종료한다.

 

연산이 끝나고 killcnt가 갱신되었다면(사거리 내 궁수가 존재한다면 살해 리스트에 해당 적의 위치를 추가한다.

2-2-2. 해당 적을 사살하고, 그 수를 센다.

            //선택당한 적 처치 -> 처치 당 kill 수 추가

            //중복 여부 확인
            List<Node> killed = new ArrayList<>();
            for (Node target : kill) {
                boolean dup = false;
                for (Node dead : killed) {
                    if (target.y == dead.y && target.x == dead.x) {
                        dup = true;
                        break;
                    }
                }

                if (!dup) {
                    cnt++;
                }
                map2[target.y][target.x] = 0;
                killed.add(target);
            }

문제의 조건에서 여러 명의 궁수는 동시에 화살을 발사하고, 여러 궁수가 하나의 적을 공격할 수 있다고 하였다. 이에 따라 처치할 적의 중복 여부를 확인하여 중복을 세지 않고 잡은 적의 수를 세어준다.

2-2-3. 모든 적을 아래로 한 칸 이동시킨다.

            //적이 아래로 한 칸씩 이동
            for (int i = n - 1; i >= 0; i--) {
                for (int j = 0; j < m; j++) {
                    if (map2[i][j] == 1) {
                        map2[i][j] = 0;
                        if (i != n - 1) {
                            map2[i + 1][j] = 1;
                        }
                    }
                }
            }
            
            //모든 적이 제거되었는지 확인
            boolean allKill = true;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map2[i][j] == 1) {
                        allKill = false;
                        break;
                    }
                }

                if (!allKill) {
                    break;
                }
            }

            if (allKill) {
                ans = Math.max(ans, cnt);
                break;
            }

적이 겹치지 않게 가장 아랫줄로부터 적들을 아래로 한 칸 이동시킨다. 맨 아래의 적이 이동할 경우 문제의 조건에 따라 제외한다. 이후 모든 적을 제거할 때 까지 반복한다.

모든 적이 제거되었다면 적을 잡은 수의 최댓값을 갱신하고 사냥 연산을 종료한다.

        System.out.println(ans);

모든 연산이 끝나고 갱신된 ans를 출력하여 정답을 구한다.

3. 코드 전문

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

public class Main {

    static int n;
    static int m;
    static int d;

    //0: 빈 공간, 1: 적 위치
    static int[][] map;

    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    static int ans = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        n = Integer.parseInt(tokenizer.nextToken());
        m = Integer.parseInt(tokenizer.nextToken());
        d = Integer.parseInt(tokenizer.nextToken());

        map = new int[n][m];

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


        boolean[] archer = new boolean[m];
        combine(m, 0, archer);

        System.out.println(ans);

    }

    private static void combine(int m, int cnt, boolean[] archer) {

        //적 사냥 수행
        if (cnt == 3) {
            hunt(archer);
            return;
        }

        //궁수의 위치 선정
        for (int i = 0; i < m; i++) {

            if (!archer[i]) {
                archer[i] = true;
                combine(m, cnt + 1, archer);
                archer[i] = false;
            }
        }

    }

    private static void hunt(boolean[] archer) {

        int[][] map2 = new int[n + 1][m];

        //map 복사
        for (int i = 0; i < n; i++) {
            System.arraycopy(map[i], 0, map2[i], 0, m);
        }

        List<Integer> arc = new ArrayList<>();
        //궁수 및 성 위치 선정
        for (int i = 0; i < m; i++) {
            if (archer[i]) {
                map2[n][i] = 2;
                arc.add(i);
            } else {
                map2[n][i] = -1;
            }
        }


        //적 처치 횟수
        int cnt = 0;

        while (true) {

            //각 궁수에 대해 bfs를 돌려서 처리할 적 선택
            List<Node> kill = new ArrayList<>();

            for (Integer ar : arc) {

                boolean[][] visit = new boolean[n + 1][m];

                Queue<Node> qu = new ArrayDeque<>();

                qu.offer(new Node(n, ar, 0));
                visit[n][ar] = true;
                int killy = 987654321;
                int killx = 987654321;
                int killcnt = 987654321;

                while (!qu.isEmpty()) {

                    Node cur = qu.poll();

                    //적을 만난 시점에서 더 진행해봐야 거리가 멀어지므로 조건에 부합하지 않게 됨 -> bfs stop
                    if (map2[cur.y][cur.x] == 1) {
                        if (cur.cnt < killcnt) {
                            killy = cur.y;
                            killx = cur.x;
                            killcnt = cur.cnt;
                        } else if (cur.cnt == killcnt && cur.x < killx) {
                            killy = cur.y;
                            killx = cur.x;
                            killcnt = cur.cnt;
                        }

                        continue;
                    }

                    //궁수와의 거리가 d -> 더 이상 늘어날 수 없음
                    if (cur.cnt == d) {

                        continue;
                    }


                    //상하좌우에 대해 bfs 방문
                    for (int i = 0; i < 4; i++) {
                        int ny = cur.y + dy[i];
                        int nx = cur.x + dx[i];

                        //map 범위 확인
                        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

                        if (!visit[ny][nx]) {
                            visit[ny][nx] = true;
                            qu.offer(new Node(ny, nx, cur.cnt + 1));
                        }
                    }

                }

                //거리의 갱신 -> 사거리 내에 적이 존재함
                if (killcnt != 987654321) {
                    kill.add(new Node(killy, killx, killcnt));
                }

            }

            //선택당한 적 처치 -> 처치 당 kill 수 추가

            //중복 여부 확인
            List<Node> killed = new ArrayList<>();
            for (Node target : kill) {
                boolean dup = false;
                for (Node dead : killed) {
                    if (target.y == dead.y && target.x == dead.x) {
                        dup = true;
                        break;
                    }
                }

                if (!dup) {
                    cnt++;
                }
                map2[target.y][target.x] = 0;
                killed.add(target);
            }

            //적이 아래로 한 칸씩 이동
            for (int i = n - 1; i >= 0; i--) {
                for (int j = 0; j < m; j++) {
                    if (map2[i][j] == 1) {
                        map2[i][j] = 0;
                        if (i != n - 1) {
                            map2[i + 1][j] = 1;
                        }
                    }
                }
            }

            //모든 적이 제거되었는지 확인
            boolean allKill = true;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map2[i][j] == 1) {
                        allKill = false;
                        break;
                    }
                }

                if (!allKill) {
                    break;
                }
            }

            if (allKill) {
                ans = Math.max(ans, cnt);
                break;
            }
        }

    }


}

class Node {
    int y;
    int x;
    int cnt;

    public Node(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}