[백준]17135. 캐슬 디펜스 - Java

📄 링크

캐슬 디펜스

---

💡 문제 분석

1. M열 중에 궁수를 배치할 3열을 뽑습니다. (조합)
2. 게임을 할 때마다 원래 배열을 유지해야 하기 때문에 미리 복사를 하고 시작합니다
3. 가장 아래 행부터 한 칸씩 위로 올라가며 궁수 위치 한 칸 위에서 BFS로 제거할 적을 선택합니다
   1. bfs 거리를 늘려가며 사정거리보다 커지면 종료시킵니다
   2. 왼쪽 적을 우선적으로 선택하기 때문에, 방향 배열의 순서가 중요합니다
4. 동시에 같은 적을 쏠 수 있기 때문에 미리 체크를 해놓고 한꺼번에 제거했습니다
5. 가장 많은 적을 없앤 경우를 출력합니다

---

⌨️ 코드

public class _17135_캐슬디펜스 {
    static int N, M, D, ret = 0;
    static int[] pick, dy = {0, -1, 0}, dx = {-1, 0, 1};
    static int[][] map, tmp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        D = sc.nextInt();
        map = new int[N][M];
        tmp = new int[N][M];
        pick = new int[3];
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                tmp[i][j] = map[i][j];
            }
        simulation(0, 0);
        System.out.println(ret);
    }

    static void simulation(int idx, int cnt) {
        if(cnt == 3) {
            ret = Math.max(ret, game());
            return;
        }
        if(idx == M) return;
        pick[cnt] = idx;
        simulation(idx + 1, cnt + 1);
        simulation(idx + 1, cnt);
    }

    static int game() {
        int sum = 0;
        for(int i = 0; i < N; i++) map[i] = tmp[i].clone();
        for(int i = N - 1; i >= 0; i--) {
            for(int a = 0; a < 3; a++) {
                int cur = pick[a];
                if (map[i][cur] != 0) map[i][cur]++;
                else bfs(i, cur);
            }
            sum += count(i);
        }
        return sum;
    }

    static void bfs(int y, int x) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        visited[y][x] = true;
        q.add(new Point(x, y));
        int cnt = 1;
        while (!q.isEmpty()) {
            int s = q.size();
            if (cnt > D) return;
            for (int c = 0; c < s; c++) {
                Point p = q.poll();
                if (map[p.y][p.x] != 0) {
                    map[p.y][p.x]++;
                    return;
                }
                for (int d = 0; d < 3; d++) {
                    int ny = p.y + dy[d], nx = p.x + dx[d];
                    if (ny < 0 || nx < 0 || nx >= M || visited[ny][nx]) continue;
                    visited[ny][nx] = true;
                    q.add(new Point(nx, ny));
                }
            }
            cnt++;
        }
    }

    static int count(int y) {
        int sum = 0;
        for(int j = y; j >= 0; j--)
            for(int k = 0; k < M; k++)
                if(map[j][k] > 1) {
                    sum++;
                    map[j][k] = 0;
                }
        return sum;
    }
}

---

📋 결과