[백준] 17135 - 캐슬 디펜스 (java)

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

예제 입력

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

예제 출력

3

코드

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
	int x, y;

	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Node o) {
		return this.y - o.y;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node other = (Node) obj;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}

}

public class Main {
	static int N, M, D;
	static int[][] origin_map, map;
	static boolean[] visited;
	static ArrayList<Node> origin_enemy;
	static ArrayList<Node> enemy;
	static int answer;

	static int[] dx = { 0, -1, 0 };
	static int[] dy = { -1, 0, 1 };

	public static void main(String[] args) throws Exception {
		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());
		origin_map = new int[N + 2][M + 1];
		map = new int[N + 2][M + 1];
		visited = new boolean[M + 1];
		origin_enemy = new ArrayList<>();

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++) {
				origin_map[i][j] = Integer.parseInt(st.nextToken());

				if (origin_map[i][j] == 1) {
					origin_enemy.add(new Node(i, j));
				}
			}
		}

		setLocation(0);

		bw.write(answer + "\n");

		br.close();
		bw.close();
	}

	public static void setLocation(int cnt) {
		if (cnt == 3) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					map[i][j] = origin_map[i][j];
				}
			}
			enemy = new ArrayList<>();

			for (Node o : origin_enemy) {
				enemy.add(new Node(o.x, o.y));
			}

			startGame();
            		return;
		}

		for (int i = 1; i <= M; i++) {
			if (!visited[i]) {
				visited[i] = true;
				setLocation(cnt + 1);
				visited[i] = false;
			}
		}
	}

	public static void startGame() {
		int killCnt = 0;

		while (enemy.size() > 0) {
			ArrayList<Node> removeList = new ArrayList<>();
			for (int i = 1; i <= M; i++) {
				if (visited[i]) {
					Node point = getMin(N + 1, i);
					if (point != null) {
						removeList.add(point); // 궁수에게 가장 가까운 곳
					}
				}
			}

			for (Node r : removeList) {
				if (map[r.x][r.y] != 0) {
					map[r.x][r.y] = 0;
					enemy.remove(new Node(r.x, r.y));

					killCnt++;
				}
			}

			move(); // 적 이동
		}

		answer = Math.max(answer, killCnt);
	}

	public static Node getMin(int x, int y) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(x, y));

		int cnt = 0;
		while (cnt < D) {
			PriorityQueue<Node> temp0 = new PriorityQueue<>();
			PriorityQueue<Node> temp1 = new PriorityQueue<>();

			while (!pq.isEmpty()) {
				Node cur = pq.poll();
				for (int i = 0; i < 3; i++) {
					int nx = cur.x + dx[i];
					int ny = cur.y + dy[i];
					if (nx > 0 && nx <= N && ny > 0 && ny <= M) {
						if (nx != x) {
							if (map[nx][ny] == 0) {
								temp0.add(new Node(nx, ny));
							} else {
								temp1.add(new Node(nx, ny));
							}
						}
					}
				}
			}

			if (temp1.size() > 0) {
				return temp1.poll();
			}

			pq.addAll(temp0);
			cnt++;
		}

		return null;
	}

	public static void move() {
		ArrayList<Node> temp = new ArrayList<>();
		for (int i = 0; i < enemy.size(); i++) {
			if (enemy.get(i).x == N) {
				temp.add(enemy.get(i));
			} else {
				enemy.get(i).x += 1;
			}

		}
		for (Node t : temp) {
			enemy.remove(t);
		}

		for (int i = N; i >= 1; i--) {
			for (int j = 1; j <= M; j++) {
				map[i][j] = map[i - 1][j];
			}
		}
	}
}

정리

setLocation(): 궁수를 둘 3자리를 고른다. (dfs를 통해 조합)
startGame(): 적이 모두 사라질 때까지 게임을 진행하고 최대로 많이 죽였으면 갱신한다.
getMin(): 궁수의 처음 위치에서 출발하여 가장 가까운 노드를 찾는다. (bfs를 통해 이동)
PriorityQueue를 사용해 y 값이 작은 순으로 자동 정렬됨
move(): 적의 위치를 아래로 한칸 이동시키고 범위를 벗어나면 제거한다. map도 아래로 한칸 이동시킨다.

✔️ 주의할 점

• addAll()을 사용했더니 shallow copy가 되어 enemy를 바꿨을 때 origin_enemy까지 바뀌는 일이 발생하였다. deep copy를 원할 때는 주의해서 하나씩 컬렉션에 추가해 줘야겠다.
• dfs 내에서 return을 하지 않는 처참한 실수를 저질렀다. 사소한 실수를 저지르지 않도록 조심하자.
• 키보드에 손대기 전에 시간 복잡도도 고려해보는 습관을 기르자.