[Java] 백준 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

예제 입력 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

예제 출력 1

3

예제 입력 2

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

예제 출력 2

3

예제 입력 3

5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

예제 출력 3

5

예제 입력 4

5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

예제 출력 4

15

예제 입력 5

6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

예제 출력 5

9

예제 입력 6

6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

예제 출력 6

14

 

소스코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;

	private static int N, M, D, maxVal = Integer.MIN_VALUE;
	private static int[][] map;
	private static int[][] playmap;
	private static int[] dx = { 0, -1, 0 };
	private static int[] dy = { -1, 0, 1 };
	private static boolean[][] toAttack;

	public static void main(String[] args) throws IOException {

		bf = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		map = new int[N + 1][M];

		for (int r = 0; r < N; r++) {
			st = new StringTokenizer(bf.readLine());
			for (int c = 0; c < M; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		archerComb(3, new int[3], 0);
		System.out.println(maxVal);
	}

	// 궁수 3명 위치 조합 구하기
	public static void archerComb(int toChoose, int[] choosed, int start) {
		if (toChoose == 0) {
			play(choosed);
			return;
		}

		for (int i = start; i < M; i++) {
			choosed[choosed.length - toChoose] = i;
			archerComb(toChoose - 1, choosed, i + 1);
		}
	}

	public static void play(int[] choosed) {
		int killCnt = 0;
		playmap = new int[N + 1][M];
		for (int i = 0; i < N; i++) {
			playmap[i] = Arrays.copyOf(map[i], map[i].length);
		}

		for (int i = 0; i < N; i++) {
			searchEnemy(choosed);
			killCnt += kill(toAttack);
			move();
		}

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

	// 가장 가까운 적 구하기
	public static void searchEnemy(int[] choosed) {
		toAttack = new boolean[N][M];

		for (int i : choosed) {
			if (playmap[N - 1][i] == 1) {
				toAttack[N - 1][i] = true;
			} else {
				bfs(new Point(N - 1, i), toAttack);
			}
		}
	}

	public static void bfs(Point point, boolean[][] toAttack) {
		Queue<Point> queue = new LinkedList<>();
		queue.offer(point);

		boolean[][] visited = new boolean[N][M];
		visited[point.x][point.y] = true;

		for (int d = 1; d < D; d++) {
			int size = queue.size();
			for (int s = 0; s < size; s++) {
				Point p = queue.poll();

				for (int i = 0; i < 3; i++) {
					int nx = p.x + dx[i];
					int ny = p.y + dy[i];

					if (isIn(nx, ny) && !visited[nx][ny]) {
						if (playmap[nx][ny] == 1) {
							toAttack[nx][ny] = true;
							return;
						}
						visited[nx][ny] = true;
						queue.offer(new Point(nx, ny));
					}
				}
			}
		}
	}

	// 적 죽이기
	public static int kill(boolean[][] toAttack) {
		int killCnt = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if (toAttack[r][c]) {
					playmap[r][c] = 0;
					killCnt++;
				}
			}
		}
		return killCnt;
	}

	// 남은 적 이동하기
	public static void move() {
		for (int r = N - 1; r >= 0; r--) {
			for (int c = 0; c < M; c++) {
				if (playmap[r][c] == 1) {
					playmap[r][c] = 0;
					if (r + 1 < N) {
						playmap[r + 1][c] = 1;
					}
				}
			}
		}

	}

	public static boolean isIn(int r, int c) {
		return r >= 0 && r < N && c >= 0 && c < M;
	}
}

다양한 알고리즘이 골고루 사용되어 어려웠던 문제입니다.

1. 궁수 3명의 위치를 구합니다. - 조합 이용

2. 3명의 궁수 각각에 대해 가장 가까운 적을 탐색합니다. - bfs 이용

(이때, 가장 가까운 적이 겹칠 수도 있기 때문에 바로 count 하지 않고 boolean 배열을 이용하여 먼저 탐색을 끝낸 후에 count 해줍니다.)

3. 탐색한 적들을 죽입니다. - 완전 탐색

4. 남은 적들의 y값을 1씩 증가시킵니다.

5. 위 과정을 맵의 y값 크기인 N만큼 반복합니다.

(이때, 각 궁수 조합에 대해 제거할 수 있는 적의 최댓값을 구해주기 위해 초기 맵 정보를 복사한 playmap을 이용해줍니다.)

6. 각 조합에 대해 위 과정을 끝낼 때마다 제거할 수 있는 적의 수가 더 큰 값을 저장합니다.