[백준] 17135: 캐슬 디펜스 (BFS, Bruteforce algorithm) - JAVA

삼성 A형 기출문제

https://www.acmicpc.net/problem/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은 적이 있는 칸이다.

6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

 

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

9

 

 

# 필요개념

이 문제를 풀기 위해서 생각해야 하는 부분은 크게 2가지였다.

 

1. M개의 열 중 3명의 궁수를 배치하는 방법

2. 가장 가까운 적을 공격하고, 거리가 같다면 가장 왼쪽에 있는 적을 공격해야 한다

 

1번의 경우에 많이 고민을 했었는데, M은 최대 15까지만 들어올 수 있다는 것을 보고 그냥 모든 경우의 수를 돌려봐도 괜찮겠다는 생각이 들었다. 15C3이면 주어진 시간 대비 그냥 돌려봐도 충분하다고 판단했다.

 

2번 조건을 대충봐서 조금 오래걸렸다. 그냥 dfs를 쓰다가 이 조건을 보고 bfs를 사용하는 것으로 방식을 변경했다. bfs를 사용하고, 탐색하는 순서를 왼쪽, 앞, 오른쪽 순으로 탐색하도록 하면 2번 조건을 만족할 수 있을 것이라 판단했다.

 

 

게임판(maps) 생성

이차원 배열에 입력받은 값들을 받고, 적의 경우 따로 HashMap에 저장해두었다. index는 중복 없이 가질 수 있게 M * i + j로 지정해두어 조회하는 속도를 높이려 했다. 게임판의 값을 직접 바꾸면 모든 경우의 수마다 배열을 새로 생성해야 하기 때문에, 적이 죽었는지 여부를 판단하기 위해 Map을 사용해주었다. (true면 존재, false면 죽음)

 

 

main

이거를 함수로 뺄 수 있었겠지만,, 일단 정답코드를 짜는 것에 집중했다.

모든 경우를 탐색하도록 하고 죽인 적의 수를 반환하도록 해서 max값을 찾아 출력한다.

 

 

궁수를 특정 위치에 고정한 후 게임 시작

i, j, k는 각 궁수의 x좌표이다. 한 턴이 지날 떄마다 적이 내려오는데, 나는 궁수의 위치를 올려서 궁수보다 y좌표가 작은 경우만 처리해주었다. 각 궁수가 처리해야하는 적의 인덱스를 반환하도록 하여 해당 인덱스가 0보다 큰 경우 (실제 인덱스를 반환한 경우) 실제 처리 (map의 value를 false로 변경) 해주었다.

 

- move : 처리할 적의 인덱스를 찾는 함수

- killEnemy : 해당 인덱스를 가진 적을 처리하는 함수

 

실제 제거할 적 탐색

함수 이름을 잘못지은 거 같아 아쉽지만,,,, dis는 움직일 수 있는 최대 거리, limit은 궁수의 y좌표이다. limit보다 작은 y를 갖는 적만 탐색한다.

탐색 알고리즘은 bfs를 사용해주었다. 적을 찾은 경우 적의 인덱스를 바로 리턴하고, 적을 못찾으면 계속 탐색한다.

 

코드 라인이 너무 많은 거 같아서 마음에 들지 않지만 꽤 오래동안 못 푼 문제를 풀어서 기분이 좋다!

 

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] maps;
    static Map<Integer, Boolean> enemies = new HashMap<>();
    static int[] dy = new int[]{0, -1, 0};
    static int[] dx = new int[]{-1, 0, 1};
    static int N;
    static int M;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        makeMaps(br);

        int ans = 0;
        for (int i = 1 ; i <= M ; i++) {
            for (int j = i + 1 ; j <= M ; j++) {
                for (int k = j + 1 ; k <= M ; k++) {
                    initMap();
                    int killCount = playGame(i, j, k, D);
                    ans = Math.max(ans, killCount);
                }
            }
        }
        System.out.println(ans);
    }

    private static int playGame(int i, int j, int k, int dis) {
        int cnt = 0;
        int nowY = maps.length;
        while (nowY > 1) {
            int fstNodeidx = move(nowY, i, dis, nowY);
            int scdNodeidx = move(nowY, j, dis, nowY);
            int trdNodeidx = move(nowY, k, dis, nowY);
            cnt += (killEnemy(fstNodeidx) + killEnemy(scdNodeidx) + killEnemy(trdNodeidx));

            nowY--;
        }

        return cnt;
    }

    private static int move(int y, int x, int dis, int limit) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{y, x, dis});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int distance = node[2];
            if (distance <= 0) continue;

            for (int i = 0 ; i < 3 ; i++) {
                int ny = node[0] + dy[i];
                int nx = node[1] + dx[i];
                int idx = ny * M + nx;
                if (canGo(ny, nx, limit)) {
                    if (enemies.get(idx) != null && enemies.get(idx)) {
                        return idx;
                    } else {
                        queue.add(new int[]{ny, nx, distance - 1});
                    }
                }
            }
        }

        return 0;
    }

    private static int killEnemy(int idx) {
        if (idx > 0 && enemies.get(idx)) {
            enemies.put(idx, false);
            return 1;
        }
        return 0;
    }

    private static boolean canGo(int y, int x, int limitY) {
        return y > 0 && y < limitY && x > 0 && x <= M;
    }

    private static void initMap() {
        enemies.replaceAll((key, value) -> {
            if (!value) return true;
            return value;
        });
    }

    private static void makeMaps(BufferedReader br) throws IOException {
        maps = new int[N + 1][M + 1];
        for (int i = 1 ; i <= N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1 ; j <= M ; j++) {
                int idx = M * i + j;
                maps[i][j] = Integer.parseInt(st.nextToken());
                if (maps[i][j] == 1) {
                    enemies.put(idx, true);
                }
            }
        }
    }


}

 

 

# 결과