[[Baekjoon] 17135 – 캐슬 디펜스](https://www.acmicpc.net/problem/17135)
티어 및 알고리즘 분류
- 티어: 골드 3
- 알고리즘 분류
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
문제 접근 방식
- 입력 및 초기 맵 구성: 입력으로 게임판의 크기, 궁수의 사거리, 적의 위치 정보를 받아 2차원 배열에 저장한다.
- 궁수 위치 조합 생성 (조합, Combination): M개의 열 중 3개의 열을 선택하여 궁수 배치를 결정한다. 재귀를 이용해 모든 조합(최대 455개)을 생성한다.
- 각 궁수 배치에 대한 게임 시뮬레이션: 각 조합별로 맵을 복사하여 독립적인 시뮬레이션을 진행한다.
- 궁수 공격 순서 계산 (BFS): 각 궁수의 위치에서 공격 가능한 범위를 BFS를 통해 미리 계산한다. 거리가 가까운 순서, 왼쪽 우선 순서를 따른다.
- 게임 진행: 매 턴마다 각 궁수가 공격할 적을 선택하고, 같은 적에 대해 중복 처리를 한 후 적을 제거한다. 턴이 종료되면 적이 아래로 한 칸씩 이동한다.
- 최대 처치 수 계산: 모든 궁수 조합에 대해 시뮬레이션한 후 최대 처치 수를 결과로 출력한다.
구현 코드
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class Sol17135 {
static Set<Integer[]> combList = new HashSet<>();
static int[][] map;
public static void main(String[] args) {
//초기 데이터 입력
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int d = sc.nextInt();
int resultCount = 0;
//map 함수 입력
map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
//궁수의 위치 조합을 구함
Integer[] sel = new Integer[m];
Arrays.fill(sel, 0);
combination(0, 0, sel, m);
//모든 궁수 위치 조합을 반복함
for (Integer[] archerOrder : combList) {
//해당 라운드 맵 복사
int[][] cMap = new int[n][m];
for(int i = 0; i < map.length;i++){
for(int j = 0; j < map[i].length;j++){
cMap[i][j] = map[i][j];
}
}
//현재 적 처치 저장 변수
int cEnemyCount = 0;
//3명의 궁수의 공격 범위 및 순서를 저장함
List<List<Integer[]>> archersAttackOrders = new ArrayList<>();
for (int i = 0; i < archerOrder.length; i++) {
if (archerOrder[i] == 1) {
archersAttackOrders.add(findAttackOrder(n, i, d, n, m));
}
}
while (true) {
//모든 적이 제외되면 게임 오버
if (checkGameOver(cMap)) {
break;
}
//1 round에 공격한 적 저장
Set<Integer[]> cAttacked = new HashSet<>();
//3명의 궁수가 적을 공격
for(List<Integer[]> archersAttackOrder: archersAttackOrders){
for(Integer[] attackOrder:archersAttackOrder){
//만약 해당 순서에 해당 위치가 적이면 공격한 적에 저장
if(cMap[attackOrder[0]][attackOrder[1]] == 1){
cAttacked.add(attackOrder);
break;
}
}
}
//공격 당한 적
for(Integer[] attackedPos : cAttacked){
if(cMap[attackedPos[0]][attackedPos[1]] == 1){
cMap[attackedPos[0]][attackedPos[1]] = 0;
cEnemyCount += 1;
}
}
//적이 한칸씩 다가옴
moveEnemy(cMap,n,m);
}
if(cEnemyCount > resultCount){
resultCount = cEnemyCount;
}
}
System.out.println(resultCount);
}
static boolean checkGameOver(int[][] cmap) {
for (int i = 0; i < cmap.length; i++) {
for (int j = 0; j < cmap[i].length; j++) {
if (cmap[i][j] == 1) {
return false;
}
}
}
return true;
}
static void moveEnemy(int[][] cmap, int n, int m){
for(int i = n-1; i>=0; i--){
for(int j = m-1;j >=0; j--){
if(i == n-1 && cmap[i][j] == 1){
cmap[i][j] = 0;
}else if(cmap[i][j] == 1){
cmap[i][j] = 0;
cmap[i+1][j] = 1;
}
}
}
}
static List<Integer[]> findAttackOrder(int x, int y, int d, int n, int m) {
//궁수 공격 범위 및 순서 정의
List<Integer[]> attackOrder = new ArrayList<>();
//BFS 초기 값 설정 및 방문배열 초기화화
Queue<Integer[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[n][m];
int order = 1;
queue.offer(new Integer[]{x - 1, y});
//공격 순서에 넣기
attackOrder.add(new Integer[]{x - 1, y});
visited[x - 1][y] = true;
while (!queue.isEmpty()) {
//다음 레이어 순서를 저장하는 queue
Queue<Integer[]> temp = new ArrayDeque<>();
//레이어 순서 변경
order += 1;
//공격할 수 있는 범위까지만 순서를 정함
if (order > d) {
break;
}
//한 레이어를 다 돌림
while (!queue.isEmpty()) {
Integer[] cPos = queue.poll();
//3방향 넣기
for (int i = 0; i < 3; i++) {
int dx = cPos[0];
int dy = cPos[1];
if (i == 0) {//왼쪽
dy--;
} else if (i == 1) {//위쪽
dx--;
} else {//오른쪽
dy++;
}
if (dx >= 0 && dx < n && dy >= 0 && dy < m && !visited[dx][dy]) {
temp.offer(new Integer[]{dx, dy});
//공격 순서에 넣기
attackOrder.add(new Integer[]{dx, dy});
//넣고 방문 처리
visited[dx][dy] = true;
}
}
}
//다 넣었으면 queue에 다음 레이어 추가
queue = new ArrayDeque<>(temp);
temp.clear();
}
return attackOrder;
}
static void combination(int idx, int count, Integer[] sel, int m) {
//3개의 궁수 위치를 모두 선택했다면, 현재 조합을 저장
if (count == 3) {
combList.add(Arrays.copyOf(sel, m));
return;
}
//더 이상 선택할 위치가 없다면 종료
if (idx == m) {
return;
}
// 선택된
sel[idx] = 1;
combination(idx + 1, count + 1, sel, m);
// 선택 안된
sel[idx] = 0;
combination(idx + 1, count, sel, m);
}
}풀이 과정 상세 설명
- 입력 및 초기화
Scanner를 이용하여 게임판의 크기(N, M), 궁수의 사거리(D)를 입력받는다.
2차원 배열 map에 적의 배치를 저장한다.
- 궁수 위치 조합 생성
M개의 열 중 3개의 열을 선택하기 위해 재귀 함수를 이용한 조합(combination)을 생성한다.
각 조합은 배열로 표현되며, 값이 1인 위치에 궁수가 배치된다.
- 각 궁수 배치에 대한 게임 시뮬레이션
각 궁수 배치 조합마다 원본 맵을 깊은 복사하여 독립적인 시뮬레이션을 진행한다.
공격 순서를 미리 계산하기 위해 각 궁수 위치에서 BFS를 수행하여 공격 순서를 정한다.
BFS에서는 거리가 가까운 순서, 거리가 같으면 왼쪽 우선 순서를 따른다.
- 게임 진행
시뮬레이션 루프를 돌며 모든 적이 제거될 때까지 진행한다.
매 턴마다 각 궁수가 미리 계산된 순서대로 공격할 수 있는 적을 탐색하여 공격한다.
한 턴에 중복 공격된 적은 한 번만 처리하며, 턴 종료 후 적이 아래로 한 칸씩 이동한다.
- 최대 처치 수 계산
각 궁수 배치 조합별로 처치한 적의 수를 기록한 후, 최대값을 최종 결과로 출력한다.
