백준 17135 캐슬 디펜스 - JAVA

17135 문제 링크

---

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

 

문제 설명

---

 

 

입출력

---

 

코드

---

< Map + BFS 활용 >

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M, D;
    static int[][] board;
    static int max = 0;
    static Map<Integer, Boolean> enemies = new HashMap<>();
    static int[] dy = {0, -1, 0};
    static int[] dx = {-1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken()); // 공격 거리 제한
        board = new int[N][M]; // 궁수 위치는 N + 1이지만 실제 board는 안쓰기 때문에 배열크기는 N으로 설정
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int idx = i * M + j;
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 1) enemies.put(idx, true);
            }
        }
        dfs(0, 0, new int[3]);
        bw.write(String.valueOf(max));
        bw.flush();
    }
    private static void dfs(int start, int idx, int[] archerPosX) {
        // 궁수 3명 배치
        if (idx == 3) {
            // 정상적인 백트래킹을 위해 적 정보 true로 초기화
            initEnemyState();
            // 이제 몇 명 지울 수 있는지 함수 호출
            int killCount = playGame(archerPosX);
            max = Math.max(max, killCount);
            return;
        }
        for (int i = start; i < M; i++) {
            archerPosX[idx] = i;
            dfs(i + 1, idx + 1, archerPosX);
        }
    }
    private static void initEnemyState() {
        enemies.replaceAll((key, value) -> {
           if (!value) return true;
           return value;
        });
    }
    private static int playGame(int[] archerPosX) {
        int archerPosY = N;
        int count = 0;
        while (archerPosY > 0) {
            int firstArcherTargetIdx = move(archerPosY, archerPosX[0], archerPosY);
            int secondArcherTargetIdx = move(archerPosY, archerPosX[1], archerPosY);
            int thirdArcherTargetIdx = move(archerPosY, archerPosX[2], archerPosY);
            count += kill(firstArcherTargetIdx) + kill(secondArcherTargetIdx) + kill(thirdArcherTargetIdx);
            archerPosY--;
        }
        return count;
    }
    private static int move(int y, int x, int limitY) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {y, x, D});
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[2] <= 0) continue;
            for (int i = 0; i < 3; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                int idx = ny * M + nx; // 적의 y위치는 궁수의 y위치보다 작아야하므로
                if (ny < 0 || nx < 0 || ny >= limitY || nx >= M) continue;
                if (enemies.get(idx) != null && enemies.get(idx)) return idx; // 한 턴에 한 번 씩만 공격하도록
                else queue.offer(new int[] {ny, nx, cur[2] - 1});
            }
        }
        return -1;
    }
    private static int kill(int idx) {
        // 적 idx가 -1이 아니고, 현재 적 idx가 true인 경우만(궁수들이 같은 적을 죽이는 것을 방지)
        if (idx >= 0 && enemies.get(idx)) {
            enemies.put(idx, false);
            return 1;
        }
        return 0;
    }
}

 

< 맨해튼 거리 계산 기반 >

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M, D;
    static int[][] board;
    static int[] archerPosX = new int[3];
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken()); // 공격 거리 제한
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int idx = i * M + j;
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
        bw.write(String.valueOf(max));
        bw.flush();
    }
    private static void dfs(int start, int idx) {
        if (idx == 3) {
            // 이제 몇 명 지울 수 있는지 함수 호출
            int killCount = playGame();
            max = Math.max(max, killCount);
            return;
        }
        for (int i = start; i < M; i++) {
            archerPosX[idx] = i;
            dfs(i + 1, idx + 1);
        }
    }
    private static int playGame() {
        int count = 0;
        int[][] status = new int[N][M];
        for (int line = N; line > 0; line--) {
            for (int posX : archerPosX) {
                for (int d = 1; d <= D; d++) {
                    int killCount = attack(status, line, posX, d);
                    if (killCount < 0) continue;
                    count += killCount;
                    break; // 한 턴에 한 번 씩만 공격하도록
                }
            }
        }
        return count;
    }
    private static int attack(int[][] status, int line, int posX, int dist) {
        for (int x = posX - dist; x <= posX + dist; x++) {
            int y = line - dist + Math.abs(x - posX);
            if (x < 0 || y < 0 || x >= M || y >= line) continue;
            if (board[y][x] == 0) continue;
            if (status[y][x] == 0) {
                status[y][x] = line;
                return 1;
            } else if (status[y][x] == line) return 0;
        }
        return -1;
    }
}

 

알고리즘 설명

---

이번 문제는 한 칸씩 아래로 전진하는 적들에 대해 어떻게 배열을 효율적으로 활용할 것인지와 각 궁수들의 위치로부터 적을 어떻게 효율적으로 없앨 것인지를 확인하는 문제입니다.

먼저, 매 턴마다 적들의 위치는 배열상 한 칸씩 내려지기 때문에, 모든 적들을 매 턴마다 내리는 것 보다는 N + 1행에 위치한 성을 매 턴마다 한 칸씩 위로 올리는 것이 효율적입니다. 이렇게하면 배열을 실제로 이동시키지 않아도, 궁수의 공격 범위(D)를 기준으로 적을 탐색할 수 있기 때문입니다. 즉, 배열을 복사하거나 이동시키는 비용없이, 매 턴 마다 성의 행을 한 칸씩 올려주면 효율적으로 문제를 풀 수 있습니다.

 

다음으로, 각 궁수의 위치에서 공격 가능한 적을 탐색하는 방법입니다. 먼저, 저는 탐색 알고리즘을 기반으로 조건에 맞춰 적을 탐색했었습니다. 하지만, 맨해튼 공식을 십분 활용하는 다른 분의 풀이를 보고, 조금 더 효율적인 풀이에 대해 고민하는 시간을 많이 가졌던 것 같습니다.

 

먼저 제가 풀이한 Map + BFS 기반 탐색입니다.

먼저 적의 위치를 HashMap에 <좌표, true>로 저장합니다. 좌표는 [r][c]이기 때문에, 하나의 숫자로 만들 필요가 있었습니다.

따라서 (r * m) + c를 사용해 2차원 좌표를 1차원 키로 변환했습니다. 이렇게 해서 적의 존재여부를 true/false로 관리했습니다.

 

각 궁수의 열의 위치를 백트래킹을 통해 중복되지 않는 모든 조합을 만들어내고, 이후 성의 행을 한 칸씩 1번 행까지 위로 올려가면서, 궁수의 1부터 D까지 사거리에 따라 적을 탐색합니다. 성의 행을 0번 행까지가 아닌 1번 행까지만 위로 올린 이유는 성이 0번 행이면 죽일 수 있는 적의 수가 없을 뿐더러, 모든 적이 맵에서 제외되어 게임이 종료되기 때문입니다.

 

궁수가 쏠 수 있는 적들의 거리가 같은 거리라면 왼쪽에 있는 적을 우선 죽여야하기때문에 왼쪽, 위쪽, 오른쪽으로 시계방향으로 BFS 탐색을 진행하며 제거할 수 있는 적의 수를 카운트하는 방식을 활용했습니다.

 

하지만 해당 방식은 BFS를 위해 '큐'라는 자료구조를 사용하는 것을 제외하고도 맵을 활용해 탐색되는 좌표에 대해 적이 존재하는지, 해당 적을 다른 궁수가 이미 쏘지는 않았는지를 Map을 활용해 관리해야하는 메모리적 부담과, 각 궁수의 위치에 따라 BFS탐색을 함에 따라서 false가 되는 Map의 키를 다시 true로 바꿔주어야 하는 로직상의 번거로움이 존재합니다.

 

그래서 제 코드를 제출하고 나서, 다른 분들의 풀이를 살펴봤습니다.

 

그 때, 볼 수 있었던 것이 거리 맨해튼 거리 계산 기반 풀이 입니다.

맨해튼 거리 공식을 이용해, 궁수의 위치에서 공격 가능한 적을 왼쪽에서 오른쪽으로 찾는 방식이었습니다.

 

궁수의 위치를 (line, posX)라고 하고, 적의 위치를 (y, x)라고 한다면 궁수가 사거리인 dist를 만족하려면 |line - y| + |posX - x|가 되어야 합니다. 먼저 적의 위치인 y는 line보다 작기 때문에 굳이 절댓값으로 만들 필요가 없습니다.

따라서 dist = line - y + Math.abs(posX - X)이므로, y와 dist의 위치를 바꾼다면 y = line - dist + Math.abs(posX - x)라고 볼 수 있습니다.

궁수가 위치하는 x좌표에서 적을 쏠 수 있는 x좌표의 범위는 posX - dist에서 posX + dist 입니다.

구해진 y와 x의 좌표를 가지고 이제 궁수가 쏠 수 있는 거리인 board[y][x]에 적이 존재하는 지와 존재하는 적을 이미 다른 궁수가 쐈는 지를 확인할 수 있습니다.

 

결과적으로 맨해튼 거리 계산 기반 방식은 BFS 기반 방식보다 코드가 단순하고 직관적이며, 속도와 메모리 면에서도 효율적이라는 장점을 가지고 있습니다.

따라서, 해당 풀이에서 적의 이동과 공격 범위 계산을 배열과 수식만으로 처리할 수 있다는 점이 핵심이며, 이를 통해 모든 궁수 조합에 대해 제거할 수 있는 적의 최대 수를 빠르게 계산 할 수 있습니다.

 

아래는 Map + BFS와 맨해튼 거리 계산 기반 풀이의 소요시간 차이입니다.

위부터 차례대로 맨해튼 거리 계산 기반 방식, Map + BFS

 

풀어가는 문제가 많아지는 만큼 공식처럼 남아버릴 수도 있는 풀이들에 대해 다시금 생각하게 하고, 생각을 좀 더 유연하게 만들어주는 풀이였던 것 같습니다. 갈 길이 멀군요...

 

코드 해석

---

먼저, 입력받은 arr[][] 배열을 기준으로 궁수의 공격 가능한 적 좌표를 매 턴 계산합니다. 각 궁수의 위치를 (line, posX)로 설정하고, 사거리 D 내에서 공격할 수 있는 적을 탐색합니다.

 

사거리 내 좌표는 맨해튼 거리 공식을 이용해 계산합니다. 구체적으로, 열 y는 posX - dist부터 posX + dist까지 순회하며, 각 열에 대응하는 행 r은 y = line - dist + |x - posX|로 계산합니다. 이렇게 계산된 (y, x) 좌표는 현재 궁수가 사거리 내에서 공격할 수 있는 위치가 됩니다.

 

탐색 과정에서 해당 위치에 적이 존재하고, 이번 턴에 아직 공격되지 않았다면 공격하고 status[y][x] 배열에 표시합니다. 한 턴 동안 각 궁수는 단 한 명만 공격할 수 있으며, 공격이 완료되면 다음 궁수로 넘어갑니다.

 

모든 궁수가 공격을 마치면 한 턴이 종료되고, 성의 행을 한 칸 위로 이동시켜 다음 턴을 준비합니다. 성이 1번 행까지 올라가면 더 이상 공격할 적이 없거나 모든 적이 제거되므로 게임은 종료됩니다.

 

각 궁수 조합마다 모든 턴을 진행하며 제거한 적 수를 누적하고, 백트래킹을 통해 모든 궁수 조합을 시도하여 최대 제거 가능한 적의 수를 갱신합니다.

 

이 방식의 장점은 BFS를 사용하지 않고도, 맨해튼 거리 계산만으로 거리 가까운 적 → 왼쪽 우선 규칙을 자연스럽게 구현할 수 있다는 점입니다. 또한 배열과 수식만으로 공격 후보를 계산하므로 연산량과 메모리 사용 측면에서 효율적이라는 특징이 있습니다.