Baekjoon/G3/17135. 캐슬 디펜스
G3) 17135. 캐슬 디펜스
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
풀이
궁수 3명의 위치를 조합으로 구한 후 궁수와 적 사이의 거리를 계산하며 진행하는 구현 문제였다.
궁수를 어느 위치에 배치할지 재귀를 통해 구한 다음 해당 위치와 적 사이의 거리를 계산해 가장 가까이 있는 적을 화살로 쏜 후, 적들이 한 칸씩 아래로 이동한다.
문제를 풀며 유의할 점이 두 가지 있었는데,
거리가 가장 가까운 적이 여러명인 경우 가장 왼쪽에 있는 적을 화살로 쏜다.
여러명의 궁수가 하나의 적을 향해 화살을 쏠 수 있다.
조건 1을 위해 Enemy 객체를 생성한 후 리스트에 집어넣고, x에 대해 오름차순, y에 대해 내림차순으로 정렬해주었다.
이렇게 정렬했을 경우 리스트를 순회하면서 가장 먼저 만나는 적이 가장 가까이 있는 적이다.
조건 2를 위해서는 적을 만날 때마다 바로 리스트에서 삭제하는 것이 아니라, Enemy 객체 내에 isHit 변수를 두어 공격을 당하는지 정보를 저장하고,
모든 궁수의 공격이 끝난 후 리스트를 순회하며 isHit 변수가 true 객체들만 리스트에서 제거해주었다.
이후 남아있는 적들에 대해 아래로 한칸 이동시키는 연산을 수행하는데, 만일 적이 격자판의 크기를 벗어난다면 마찬가지로 리스트에서 제거해주었다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, D, ans;
static List<Enemy> enemies, tmp;
static int[] archers;
static class Enemy {
int y, x;
boolean isHit;
public Enemy(int y, int x) {
this.y = y;
this.x = x;
this.isHit = false;
}
}
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
enemies = new ArrayList<>();
archers = new int[3];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
if (Integer.parseInt(st.nextToken()) == 1) {
enemies.add(new Enemy(i, j));
}
}
}
comb(0, 0);
bw.write(ans + "\n");
bw.flush();
br.close();
bw.close();
}
static void comb(int cnt, int start) {
if (cnt == 3) {
tmp = new ArrayList<Enemy>();
for (int i = 0; i < enemies.size(); i++) {
tmp.add(new Enemy(enemies.get(i).y, enemies.get(i).x));
}
Collections.sort(tmp, new Comparator<Enemy>() {
@Override
public int compare(Enemy o1, Enemy o2) {
return o1.x == o2.x ? o2.y - o1.y : o1.x - o2.x;
}
});
int sum = 0;
while (!tmp.isEmpty()) {
for (int i = 0; i < 3; i++) {
int minDist = D + 1;
int attackIdx = -1;
for (int j = 0; j < tmp.size(); j++) {
int distance = Math.abs(N - tmp.get(j).y) + Math.abs(archers[i] - tmp.get(j).x);
if (distance < minDist) {
minDist = distance;
attackIdx = j;
}
}
if (attackIdx != -1) {
tmp.get(attackIdx).isHit = true;
}
}
Iterator<Enemy> it = tmp.iterator();
while(it.hasNext()) {
Enemy cur = it.next();
if (cur.isHit) {
sum++;
it.remove();
} else if (cur.y + 1 == N) {
it.remove();
}
}
for (int i = 0; i < tmp.size(); i++) {
tmp.get(i).y++;
}
}
ans = Math.max(sum, ans);
return;
}
for (int i = start; i < M; i++) {
archers[cnt] = i;
comb(cnt + 1, i + 1);
}
}
}