[백준] [17135] 캐슬디펜스 (JAVA) (백트래킹) (구현)

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

17135번: 캐슬 디펜스

---

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

31729

11827

7151

32.848%

문제

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

 

---

※ JAVA 코드 (캐슬 디펜스)

import java.io.*;
import java.util.*;

public class Main {
    private static int N, M, D;
    private static int[][] map;
    private static int[][] tempMap;

    public static int[] archerList;

    private static ArrayList<Node> killList;

    private static int result = 0;

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

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

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int num;

        st = new StringTokenizer(br.readLine());

        // N, M : 맵범위 D : 사거리
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        // 맵 세팅
        map = new int[N + 2][M + 1];
        tempMap = new int[N + 2][M + 1];
        archerList = new int[M + 1];

        HashSet<Integer> set = new HashSet<>();
        // 맵 입력
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++) {
                num = Integer.parseInt(st.nextToken());
                map[i][j] = num;
                tempMap[i][j] = num;
            }
        }

        for(int i = 1; i <= M; i++) {
            archerList[i] = i;
        }

        setPosition(archerList, 1, 0, set);

        System.out.println(result);
    }

    // idx, pos (백트래킹 사용)
    public static void setPosition(int[] list, int idx, int pos, HashSet<Integer> set) {
        // 재귀 탈출 조건
        if(pos == 3) {
            for(int i = 1; i <= N; i++) {
                for(int j = 1; j <= M; j++) {
                    map[i][j] = tempMap[i][j];
                }
            }

            // 한 포지션에서 죽인 적군 수 누적
            int killed = 0;

            killList = new ArrayList<>();

            while(true) {
                // 맵에 없으면 탈출
                if(!chkEnermy()) {
                    break;
                } else {
                    for(int i : set) {
                        // 궁수의 위치 3군데 대입후
                        serchEnermy(N + 1, i);
                    }

                    // 한 턴에 사살 가능한 리스트 중 없어진 적 수를 구한다.
                    for(int i = 0; i < killList.size(); i++) {
                        if(map[killList.get(i).x][killList.get(i).y] == 1) {
                            map[killList.get(i).x][killList.get(i).y] = 0;
                            killed++;
                        }
                    }
                    killList = new ArrayList<>();

                    // 사살 후 적 한칸 아래로 이동
                    moveEnermy();
                }
            }

            result = Math.max(result, killed);

            return;
        }

        for(int i = idx; i <= M; i++) {
            // 중복없이 3개 선택
            set.add(i);
            setPosition(list, i + 1, pos + 1, set);
            set.remove(i);
        }
    }

    public static void serchEnermy(int x, int y) {
        boolean[][] visited = new boolean[N + 2][M + 1];
        Queue<Node> q = new LinkedList<>();
        Node now = new Node(x, y, 0);
        q.offer(now);
        visited[now.x][now.y] = true;

        while(!q.isEmpty()) {
            Node nx = q.poll();
            for(int i = 0; i < 3; i++ ) {
                int nextX = nx.x + dx[i];
                int nextY = nx.y + dy[i];
                int nextCnt = nx.cnt + 1;

                // 좌표 범위 체크
                if(nextX < 1 || nextX > N || nextY < 1 || nextY > M) continue;
                // 사정거리를 벗어난 경우
                if(nextCnt > D) continue;
                // 맵 방문 체크
                if(visited[nextX][nextY]) continue;

                Node next = new Node(nextX, nextY, nextCnt);

                if(map[nextX][nextY] == 1) {
                    // 제거 대상 적좌표 리스트에 저장
                    killList.add(new Node(nextX, nextY, 0));
                    return;
                }

                visited[nextX][nextY] = true;
                q.offer(next);
            }
        }
    }

    // 적이동
    public static void moveEnermy() {
        for(int i = N; i >= 1; i--) {
            for(int j = 1; j <= M; j++) {
                // 1칸씩 아래로 이동
                map[i][j] = map[i-1][j];
            }
        }
    }

    // 맵에 적이 있는지 체크
    public static Boolean chkEnermy() {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(map[i][j] == 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

---

※ 생각정리 (캐슬 디펜스)

[Hint] 복잡한 문제를 쪼개서 생각해보기

1. 궁수 배치 (M개중 3개의 경우의 수를 뽑는 조합을 사용)

2. 사거리가 닿는 적 탐색 (가장 가까우면서, 가장왼쪽에 있는 적 탐색)

3. 적 공격 (이때 중복이 가능함을 유의해야한다)

4. 1회 공격 후 적 아래로 한칸씩 이동

5. 2번부터 반복

---

1. 궁수 배치

M개의 열중 총 3개의 포지션에 궁수를 배치해야한다. 행의 위치는 N + 1로 고정이므로 생각할 필요가 없다.

public static void setPosition(int[] list, idx, pos, HashSet<Integer> set) {
    // M개중 3개를 뽑는 경우의 수 (재귀 탈출 조건)
    if(pos == 3) {
    	// 탈출
        return;
    }
    
    for(int i = idx; i <= M; i++) {
        // 중복없이 3개 선택
        set.add(i);
        setPosition(list, i + 1, pos + 1, set);
        set.remove(i);
    }
}

 

위 코드를 보면 알겠지만 재귀함수 사용시 무한루프방지를 위한 탈출조건을 항시 넣어준다.

또한 위 코드를 보고 수의 조합이 이해가 가지 않는다면 N과 M문제를 풀면서 이해해보기 바란다.

https://dawn-of-coding.tistory.com/189

[백준] [15649] N과 M (1) (JAVA) (백트래킹)

 

2. 사거리가 닿는 적 탐색

현재 위치(파란칸) 에서 공격할 수 있는 각 사거리를 나타낸 그림이다. 

우리는 가장가까우면서 거리가 같을 경우 가장 왼쪽인 적을 먼저 공격해야한다.

따라서, 공격할 수 있는 순서는 다음과 같다.

 

위 순서로 탐색을 하던 중 적(1)이 있는 경우 탐색을 마치고 해당 좌표를 리스트에 담아둔다.

if(map[nextX][nextY] == 1) {
    // 제거 대상 적좌표 리스트에 저장
    killList.add(new Node(nextX, nextY, 0));
    return;
}

 

이때 탐색 좌표 배열의 순서를 좌측 -> 위 -> 오른쪽 순서로 배치하여 탐색하도록 한다. 아래로는 공격하지 않을 것이므로 3개면 된다.

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

1개라도 공격할 적을 찾았을 경우 종료하는 이유는 2명이상의 적을 공격할 순없고 다른 궁수와 같은 적을 공유할 수 있기 때문이다.

 

3. 적 공격

리스트에 미리 담아둔 적의 좌표를 0으로 수정하면서 반복문을 진행한다. 중복인 좌표는 앞에서 이미 0으로 수정해버렸기 때문에 중복으로 카운팅 하지 않는다. (2명의 궁수가 1명의 적을 공격해도 죽은 적은 1명)

// 한 턴에 사살 가능한 리스트 중 없어진 적 수를 구한다.
for(int i = 0; i < killList.size(); i++) {
    if(map[killList.get(i).x][killList.get(i).y] == 1) {
        map[killList.get(i).x][killList.get(i).y] = 0;
        killed++;
    }
}
killList = new ArrayList<>();

 

적을 1턴 공격했다면 담아둔 킬 리스트를 초기화 한다.

 

4. 적 이동

한턴의 공격이 끝나고 적은 아래로 한칸씩 이동할 수 있다.

// 적이동
public static void moveEnermy() {
    for(int i = N; i >= 1; i--) {
        for(int j = 1; j <= M; j++) {
            // 1칸씩 아래로 이동
            map[i][j] = map[i-1][j];
        }
    }
}

 

5. 한턴의 공격이 끝나고 새로운 공격시작전 맵에 남아있는 적이 있는지 확인해준다.

// 맵에 적이 있는지 체크
public static Boolean chkEnermy() {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            if(map[i][j] == 1) {
                return true;
            }
        }
    }
    return false;
}

 

 

- 새벽코딩 -