220819 - 캐슬 디펜스

◾ 캐슬 디펜스 : 백준 17135번 (골드 3)

• https://www.acmicpc.net/problem/17135

문제

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

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

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

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

---

입력

• 첫째 줄 : 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D.
  • 3 ≤ N, M ≤ 15.
  • 1 ≤ D ≤ 10.
• 이후 N 줄 : 격자판의 상태.
  • 0 : 빈 칸.
  • 1 : 적이 있는 칸.

출력

• 궁수의 공격으로 제거할 수 있는 적의 최대 수.

입출력 예

Input	Output
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

---

◾ 풀이

1. 해설

• 궁수 위치에 따라 제거할 수 있는 적의 수 계산하여 탐색.(완전 탐색.)
  • 궁수의 위치를 조합으로 탐색.
  • 궁수별 적의 위치를 우선순위 큐에 담아 가까이에 있는 적부터 제거.
  • 적이 움직일 수 있는 거리의 최대는 행 크기. => 행 크기만큼 공격 가능.
• 우선순위 큐 구성 : 적의 위치에 따라 1차 정렬. 열 위치에 따라 2차 정렬.
  • 가장 가까운 적.
  • 가장 가까운 적이 많다면 가장 왼쪽의 적.

---

2. 프로그램

1. 행렬 크기, 공격 제한 거리, 보드 입력.
2. 궁수 위치, 우선순위 큐, 방문 행렬 초기화.
3. 궁수별 적에 대한 정보 우선순위 큐에 추가.
4. 범위를 벗어나거나 이미 제거된 적을 제거하고 적을 제거해 횟수 증가.
5. 제거한 적의 수를 확인하여 큰 값으로 변경.
6. 가능한 모든 조합을 통해 탐색. (Next Permutation을 활용해 조합 탐색)

# 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 적의 정보를 담을 클래스.
class Enemy implements Comparable<Enemy> {
	int row; // 행 좌표.
	int col; // 열 좌표.
	int distance; // 궁수로부터의 거리.

	public Enemy(int row, int col, int distance) {
		super();
		this.row = row;
		this.col = col;
		this.distance = distance;
	}

	// 정렬 기준
	// 1. 거리 기준 오름차순.
	// 2. 열 기준 오름차순.(왼쪽부터)
	@Override
	public int compareTo(Enemy o) {
		int res = this.distance - o.distance;
		if (res == 0)
			return this.col - o.col;
		return res;
	}
}

public class Main {
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		st = new StringTokenizer(in.readLine());
		// 행렬 크기.
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		// 거리 제한.
		int d = Integer.parseInt(st.nextToken());

		// 보드 입력.
		// - 궁수 자리를 추가하기 위해 [행 크기 + 1]
		int[][] board = new int[n + 1][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < m; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 궁수 1, 2, 3에 대한 적들과의 거리 우선순위큐.
		// - 거리 기준 오름차순(가까운 것 부터) -> 열 기준 오름차순(왼쪽부터)
		PriorityQueue<Enemy> b1 = new PriorityQueue<>();
		PriorityQueue<Enemy> b3 = new PriorityQueue<>();
		PriorityQueue<Enemy> b2 = new PriorityQueue<>();

		// 궁수 위치 초기화
		// - Next Permutation을 활용하기 위해 위치 초기화.
		board[n][0] = 1;
		board[n][1] = 1;
		board[n][2] = 1;
		// 궁수의 열 좌표를 담을 배열.
		int[] bCols = new int[3];
		// 방문(제거) 행렬.
		boolean[][] visited;
		int answer = Integer.MIN_VALUE;

		// 궁수의 가능한 모든 조합을 탐색.
		do {
			// 궁수 위치(열 좌표) 탐색.
			for (int c = 0, idx = 0; c < m; c++) {
				if (board[n][c] == 1) {
					bCols[idx++] = c;
				}
			}

			// 우선순위 큐 입력.
			b1.clear();
			b2.clear();
			b3.clear();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					// 적일 경우 궁수와 거리를 구하여 추가.
					if (board[i][j] == 1) {
						b1.add(new Enemy(i, j, Math.abs(n - i) + Math.abs(bCols[0] - j)));
						b2.add(new Enemy(i, j, Math.abs(n - i) + Math.abs(bCols[1] - j)));
						b3.add(new Enemy(i, j, Math.abs(n - i) + Math.abs(bCols[2] - j)));
					}
				}
			}

			// 방문(제거) 행렬 초기화.
			visited = new boolean[n][m];
			// 제거한 적의 수.
			int cnt = 0;

			// 모든 적이 보드에서 사라질 때까지 반복하기 위해 행 크기만큼 반복.
			for (int step = 0; step < n; step++) {
				// 우선순위큐가 비어있지 않다면 아래의 경우 루트 노드 제거.
				// 1. 이미 제거한 적일 경우.
				// 2. 보드를 벗어난 적일 경우.
				while (!b1.isEmpty() && (visited[b1.peek().row][b1.peek().col] || b1.peek().row + step >= n))
					b1.poll();
				while (!b2.isEmpty() && (visited[b2.peek().row][b2.peek().col] || b2.peek().row + step >= n))
					b2.poll();
				while (!b3.isEmpty() && (visited[b3.peek().row][b3.peek().col] || b3.peek().row + step >= n))
					b3.poll();

				// 루트 노드의 적이 공격 가능한 위치일 경우 제거.
				// - 이때, 방문 표시를 하여 같은 적을 2번 제거하지 않도록 조치.
				if (check(b1, visited, step, d)) {
					cnt++;
				}
				if (check(b2, visited, step, d)) {
					cnt++;
				}
				if (check(b3, visited, step, d)) {
					cnt++;
				}
			}
			answer = Math.max(answer, cnt);
		} while (np(board[n]));

		sb.append(answer);
		System.out.println(sb);
	}

	// 우선순위큐 루트 노드의 적을 제거할 수 있는지 확인.
	// - 제거할 수 있다면 방문 표시. true 반환.
	// - 제거할 수 없다면 false 반환.
	// - p : 적에 대한 정보를 담은 우선순위 큐.
	// - visited[][] : 방문 정보를 담은 2차원 배열.
	// - step : 적이 이동한 거리.
	// - d : 궁수 공격 제한 거리.
	public static boolean check(PriorityQueue<Enemy> p, boolean[][] visited, int step, int d) {
		if (!p.isEmpty() && p.peek().distance - step <= d) {
			Enemy e = p.poll();
			if (!visited[e.row][e.col]) {
				visited[e.row][e.col] = true;
				return true;
			}
		}

		return false;
	}

	// Next Permutation을 응용해 조합으로 활용.
	public static boolean np(int[] input) {
		int n = input.length;

		int i = n - 1;
		while (i > 0 && input[i - 1] <= input[i])
			--i;

		if (i == 0)
			return false;

		int j = n - 1;
		while (input[i - 1] <= input[j])
			--j;

		int temp = input[i - 1];
		input[i - 1] = input[j];
		input[j] = temp;

		int k = n - 1;
		while (i < k) {
			temp = input[i];
			input[i] = input[k];
			input[k] = temp;
			i++;
			k--;
		}

		return true;
	}
}