백준 17135번-캐슬 디펜스(JAVA)
https://www.acmicpc.net/problem/17135
17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class BJ_17135 {
static int N;
static int M;
static int D;
static int K = 3; // 궁수
static int result = Integer.MIN_VALUE;
private static void makeCombination(int[] arr, List<int[]> map, int toSelect, int[] selected, int startIdx) {
//arr = 궁수 후보 배열, map = 적 좌표 리스트, toSelect = 뽑은 궁수의 수, selected = 뽑은 궁수 조합, startIdx = 중복방지 시작 index
if (toSelect == K) {
// 이번 조합에 제거할 수 있는 적의 수
int cnt = 0;
// 원본 보존 위해 map 복사
List<int[]> temp_map = new ArrayList<int[]>();
for (int[] temp : map) {
int[] tt = Arrays.copyOf(temp, temp.length);
temp_map.add(tt);
}
// temp_map 에서 적이 모두 사라질 때까지 동작
while (temp_map.size() != 0) {
int[] attack = new int[3];
int[][] remove_obj = new int[K][2];
// 세명의 궁수가 각각
for (int j = 0; j < K; j++) {
int near = Integer.MAX_VALUE;
int near_i = Integer.MAX_VALUE;
// 모든 적 에 대해;
for (int i = 0; i < temp_map.size(); i++) {
// 궁수와 적 거리 계산
int dist = Math.abs(selected[j] - temp_map.get(i)[1]) + N - temp_map.get(i)[0];
// 궁수와 적 거리가 가장 가까운 모든 적 중에서 왼쪽 원소를 찾아야 하므로 >= 으로 비교
if (near >= dist) {
// 최단 거리가 단축되면 최단거리가 같은 적들이 reset되므로
// 제일 왼쪽 원소의 column을 저장하는 near_i도 reset 시켜줘야한다.
if (near != dist)
near_i = Integer.MAX_VALUE;
// 최단 거리 갱신
near = dist;
// 거리가 사정거리이내인 것들에서
if (near <= D) {
// 가장 가까운 적 중에서 가장 왼쪽인 적 갱신
if (near_i > temp_map.get(i)[1]) {
// near_i(=가장 왼쪽 원소의 column) 갱신
near_i = temp_map.get(i)[1];
// 가장 왼쪽 원소의 temp_map 리스트 인덱스를 저장(중복 제거에 사용)
attack[j] = i;
// 가장 왼쪽 원소의 객체 저장(적 제거에 사용)
remove_obj[j] = temp_map.get(i);
}
}
// 공격할 수 있는 대상이 없으면 적제거 반복문을 돌지 않게 값 조정
else
attack[j] = map.size();
}
}
}
// 공격 대상 중복 제거
// 중복되는 적이 적 제거 반복문을 돌지 않게 값 조정
if (attack[0] == attack[1])
attack[1] = map.size();
if (attack[1] == attack[2])
attack[2] = map.size();
if (attack[0] == attack[2])
attack[2] = map.size();
// 궁수의 적제거
for (int i = 0; i < K; i++) {
// 조정한 값(=map.size())은 반복문을 돌지 않는 조건
if (attack[i] < map.size()) {
// 적 제거, 제거한 적의 수 ++;
temp_map.remove(remove_obj[i]);
cnt++;
}
}
// ------------------------
// 성벽에 닿아 제외될 적 수 count
int rmv_cnt = 0;
for (int i = 0; i < temp_map.size(); i++) {
// 적 배열 아래로 한 칸씩
temp_map.get(i)[0] += 1;
// 성벽에 닿으면 rmv_cnt++;
if (temp_map.get(i)[0] == N) {
rmv_cnt++;
}
}
// 제외할 적 수 만큼 remove
// 성벽에 닿는 적은 가장 아랫줄에 있던 적들은 리스트의 가장 뒤에 저장된 요소들이므로
// 뒤에서부터 지워주면 된다.
for (int i = 0; i < rmv_cnt; i++) {
temp_map.remove(temp_map.size() - 1);
}
}
// 최대 제거 가능한 적의 수 갱신
if (result < cnt)
result = cnt;
return;
}
// 조합 재귀
for (int i = startIdx; i < arr.length; i++) {
selected[toSelect] = arr[i];
makeCombination(arr, map, toSelect + 1, selected, i + 1);
}
}
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());
D = Integer.parseInt(st.nextToken());
List<int[]> map = new ArrayList<int[]>();
int[][] arr = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1) {
int[] temp = new int[2];
temp[0] = i;
temp[1] = j;
map.add(temp);
}
}
}
// 가능한 궁수의 요소들 초기화
int[] archer = new int[M];
for (int i = 0; i < M; i++) {
archer[i] = i;
}
makeCombination(archer, map, 0, new int[K], 0);
System.out.println(result);
}
}
적의 좌표를 map 리스트로 받아와 궁수의 조합에 따라 게임을 진행해 최대 제거 가능한 적의 수를 갱신해 풀이해주었습니다.
최단 거리가 같으면 가장 왼쪽의 적을 제거해 주는 규칙을 구현하는 것이 까다로웠던 문제라고 생각합니다.