[BOJ/Java] 17135. 캐슬 디펜스

[BOJ/Java] 17135. 캐슬 디펜스

17135번: 캐슬 디펜스

---

문제 해석

이 문제는 격자판에 적들이 주어지고, 캐슬 디펜스 게임을 통해 궁수 3명을 배치하여 최대한 많은 적을 제거하는 전략을 구현하는 것이다. 궁수는 매 턴마다 자신의 사거리(d) 내에서 가장 가까운 적을 공격한다. 동일 거리에 여러 적이 있을 경우 가장 왼쪽 적을 공격한다. 각 턴이 끝난 후 적들은 한 칸씩 아래로 이동하고, 격자판 밖으로 나가면 제거된다. 궁수의 위치는 격자판의 맨 아래 행이고, 궁수의 위치를 최적으로 결정해 최대한 많은 적을 제거해야 한다.

풀이 과정

코드는 주어진 궁수의 배치에 대해 시뮬레이션을 수행하고, 모든 가능한 배치에 대해 최대 적 제거 수를 찾는다. 구체적인 절차는 다음과 같다

 

1. permutation 함수를 사용하여 궁수의 모든 가능한 위치 조합을 생성하고, 각 조합에 대해 게임을 시작한다.
2. startGame 함수는 초기 설정을 한 후 n번의 턴 동안 게임을 진행한다. 각 턴에서는 모든 궁수가 bfs를 사용하여 공격할 적을 찾고, 찾은 적을 제거한 후, 적들을 한 칸씩 아래로 이동시킨다.
3. BFS는 궁수의 사거리 내에서 가장 가까운 적을 찾으며, 적이 여러 명일 경우 왼쪽 적을 우선적으로 선택한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No17135;

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

public class Main {
    private int[][] map; // 게임 맵
    private static final int SIZE = 3; // 궁수의 수
    private int[] sel; // 궁수의 위치를 저장하는 배열
    private int n, m, d; // 행의 수, 열의 수, 궁수의 사거리
    private static final int[][] direction = {{0, -1}, {-1, 0}, {0, 1}}; // BFS 탐색을 위한 방향 (왼쪽, 위, 오른쪽)
    private ArrayList<Point> delList; // 한 턴에서 제거할 적의 위치를 저장하는 리스트
    private int[][] original; // 원본 맵
    private boolean[][] visited; // BFS 방문 확인을 위한 배열
    private int res; // 한 게임에서의 결과를 임시 저장
    private int ans = Integer.MIN_VALUE; // 최대 적 제거 수

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

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

        sol();
        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        sel = new int[SIZE];
        permutation(0, 0);
    }
    
	// 궁수의 위치를 결정한 후 게임을 시작한다.
    private void permutation(int k, int v) {
        if (k == SIZE) {
            startGame();
            ans = Math.max(ans, res);
            return;
        }

        for (int i = 0; i < m; i++) {
            if ((v & (1 << i)) == 0) {
                sel[k] = i;
                permutation(k + 1, v | 1 << i);
            }
        }
    }
    
    /*
    게임의 로직
    1. 전역 변수 초기화
    2. 각 궁수의 위치를 기점으로 BFS 탐색 후 적의 위치 확인
    3. 적 제거
    4. 적 위치 한 칸 전진
    5. 2~4 번을 n번 반복 ( 행의 갯수만큼 반복 시 모든 적이 전진하므로 종료 )
    */

    private void startGame() {
        init();
        for (int i = 0; i < n; i++) {
            for (int s : sel) {
                bfs(n - 1, s);
            }
            updateEnemy();
            moveForward();
        }
    }

    private void init() {
        delList = new ArrayList<>();
        res = 0;
        copy();
    }

	/*
    문제의 조건 중, 동일 거리일 경우 왼쪽 적을 우선 제거하는 조건이 있다.

    BFS 탐색의 첫 좌표를 궁수의 바로 윗좌표(궁수 R-1, 궁수 C) 로 지정할 경우,
    해당 위치에 적이 존재하면 탐색 종료

    해당 위치에 적이 존재하지 않는다면, 동 -> 북 -> 서 순서로 탐색
    전체 탐색 : 북 -> 동 -> 북 -> 서 -> 동 -> 북 -> 서 ...
    순서대로 탐색 시 거리는 1 -> 2 -> 2 -> 2 -> 3 -> 3 -> 3 ...
    따라서, 첫번째 탐색 위치를 북쪽으로 따로 지정 후 동 북 서 순으로 탐색할 경우
    거리가 동일할시 동쪽부터 적이 선택되면서 탐색 종료됨
     */
    private void bfs(int x, int y) {
        if (map[x][y] == 1) {
            delList.add(new Point(x, y));
            return;
        }

        Queue<Point> queue = new ArrayDeque<>();
        visited = new boolean[n][m];
        queue.offer(new Point(x, y, 1));

        while (!queue.isEmpty()) {
            Point p = queue.poll();

            for (int dr = 0; dr < direction.length; dr++) {
                int nx = p.x + direction[dr][0];
                int ny = p.y + direction[dr][1];
                int nd = p.d + 1;

                if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny]) continue;

                if (nd > d) return;

                if (map[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.offer(new Point(nx, ny, nd));
                }

                if (map[nx][ny] == 1) {
                    delList.add(new Point(nx, ny));
                    return;
                }
            }
        }
    }

    private void copy() {
        for (int i = 0; i < n; i++) {
            map[i] = original[i].clone();
        }
    }

    private void updateEnemy() {
        for (Point p : delList) {
            if (map[p.x][p.y] == 1) {
                map[p.x][p.y] = 0;
                res++;
            }
        }
        delList.clear();
    }

    private void moveForward() {
        for (int r = n - 1; r > 0; r--) {
            map[r] = map[r - 1].clone();
        }
        Arrays.fill(map[0], 0); // 첫 번째 행을 0으로 초기화 (적이 전진하면서 비워진 행)
    }

    class Point {
        int x, y, d;

        public Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 궁수의 위치 선택 O(m^3)과 각 시뮬레이션 O(n×m)을 고려할 때 O(m^3×n×m)로 볼 수 있다. 각 게임의 진행은 선형적으로 n회의 라운드로 구성되어 있으며, 각 라운드에서 모든 적과 궁수 위치에 대해 연산을 수행한다.

느낀점

이 문제를 통해 시뮬레이션과 조합, 그리고 BFS를 함께 사용하는 복합적인 문제 해결 방식을 경험할 수 있었다. 특히, 다양한 상태를 관리하며 최적의 결과를 도출하는 과정에서 알고리즘의 설계와 구현에 대한 깊은 이해가 필요함을 느꼈다. 게임의 각 단계에서의 세밀한 조건 처리가 결과에 큰 영향을 미치는 점도 인상적이었다.