백준 17135. 캐슬 디펜스
22 Feb 2021문제 바로가기
문제 요약
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임은 N×M인 격자판에서 진행되며 각 칸당 적은 1명씩만 있다. 격자판 N번행 바로 아래인 (N+1)번 행의 모든 칸에는 성이 있다.
성을 몰려오는 적들로부터 지키기 위해 궁수 3명을 배치하는데 각각의 궁수는 적 하나를 공격할 수 있고 모든 궁수는 동시에 적을 공격한다. 그리고 모든 궁수의 공격이 끝나면 한 턴이 끝난다.
궁수가 적을 공격하는 조건은
- 거리가 D 이하인 적 중에서 가장 가까운 적
- 그러한 적이 여럿이라면 가장 왼쪽에 있는 적을 공격
공격받은 적이나 성에 도착한 적은 게임에서 제외되며 모든 적이 격자판에서 없어지만 게임이 끝난다. 이따 궁수가 공격해서 없앨 수 있는 적의 최대수를 계산하는 문제이다.
문제 풀이 포인트
- 궁수 3명이 M 칸중에서 서있을 수 있는 경우의 수 -> 조합
- 세 자리에 서있을 때 N 번째 행부터 찾아가며 각 궁수별로 가장 최소인 적의 위치 찾아서 저장
- 세명의 궁수가 모두 끝나면 저장해둔 적을 지우고 죽인 적 카운팅. 이때 같은 적인지 판별해야함
- 한턴 끝
- 적이 한줄 내려오고 성에 도달하는 적은 없어짐
전형적인 시뮬레이션 문제로 각 턴을 기점으로 적이 서있는 배열이 변경되는 것을 잘 확인하여야 한다. 또한, 가장 중요한 문제는 궁수들끼리 같은 적을 공격하여 없앨수도 있으므로 각 궁수들이 죽일 때마다 없애는 것이 아니라 죽일 수 있는 적을 확인하고 모든 궁수의 확인이 끝나면 그때 한번에 지우는 것이 중요한 포인트라 생각한다.
문제 코드[JAVA]
코드 펼치기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M, D;
static int[][] map;
static int AC, ans; // 궁수의 행의 위치
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = parse(st.nextToken());
M = parse(st.nextToken());
D = parse(st.nextToken());
map = new int[N + 1][M];
AC = N;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = parse(st.nextToken());
}
}
combination(0, 0, new int[3]);
System.out.println(ans);
}
private static void combination(int k, int idx, int sel[]) {
// sel : 궁수의 위치를 뽑은 배열
if (k == sel.length) {
int cnt = 0;
int[][] arr = copy(map);
for (int p = 0; p < N; p++) {
ArrayList<Integer> kill_x = new ArrayList<>();
ArrayList<Integer> kill_y = new ArrayList<>();
// 각 궁수 별 최소 거리에 있는 적을 찾아서
// 죽일 적의 좌표를 리스트에 담음
for (int ar : sel) {
int[] temp = kill(ar, arr);
if(temp == null) {
continue;
}
if(kill_x.isEmpty()) {
kill_x.add(temp[0]);
kill_y.add(temp[1]);
}
else {
boolean flag = true;
for(int j = 0; j < kill_x.size(); j++) {
if(temp[0] == kill_x.get(j) &&
temp[1] == kill_y.get(j)) {
//둘중 하나라도 다르면 다른 병사
flag = false;
}
}
if(flag) {
kill_x.add(temp[0]);
kill_y.add(temp[1]);
}
}
}
// 다 담았으니까 죽여야 한다.
// 죽이려면 map의 위치에 있는 값을 0으로 변경하고 카운트 +1
for(int d = 0; d < kill_x.size(); d++) {
arr[kill_x.get(d)][kill_y.get(d)] = 0;
cnt++;
}
//다 죽였으면 한칸씩 아래로 내림
for(int i = N; i >= 0; i--) {
for(int j = 0; j < M; j++) {
if(i == 0)
arr[i][j] = 0;
else
arr[i][j] = arr[i-1][j];
}
}
}
ans = Math.max(ans, cnt);
return;
}
// 궁수의 위치를 뽑기 위한 조합
for (int i = idx; i < M; i++) {
sel[k] = i;
combination(k + 1, i + 1, sel);
}
}
// 기존 입력 배열을 복사하기 위한 메소드
private static int[][] copy(int[][] map){
int[][] arr = new int[N+1][M];
for(int i = 0; i < N; i++) {
System.arraycopy(map[i], 0, arr[i], 0, M);
}
return arr;
}
private static int[] kill(int ar, int[][] arr) {
int x = -1, y = -1;
int min = Integer.MAX_VALUE;
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < M; j++) {
// 해당 위치에 적이 있을 때
if (arr[i][j] == 1) {
int dis = Math.abs(ar - j) + Math.abs(AC - i);
if (dis <= D) {
if (min > dis) {
min = dis;
x = i;
y = j;
}
// 같은 거리에 있으면 더 왼쪽에 있는 좌표로 설정
if(min == dis) {
if(y > j) {
x = i;
y = j;
}
}
}
}
}
}
// 적의 위치가 수정되지 않으면 담지 않고 return
if(x == -1 && y == -1)
return null;
// 아니라면 적의 위치를 담아 return
else
return new int[] { x, y };
}
private static int parse(String n) {
return Integer.parseInt(n);
}
}