[백준] 17135번 캐슬 디펜스 (C++, JAVA)

17135번: 캐슬 디펜스

궁수 3명을 배치시키는 경우는

M개 중 3개를 순서 상관없이 뽑는 조합으로 구하면 된다.

 

궁수가 (5, 2)에 있을 때

공격할 수 있는 위치에 따른 거리들을 표시해 보았다.

 

궁수가 공격할 수 있는 거리는

궁수 위치에서부터 좌, 상, 우 방향으로 BFS 했을 때의

깊이와 같다는 것을 알 수 있다.

 

공격할 수 있는 적은

거리가 D 이하인 적 중에서 가장 가까운 적이고

그런 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 하므로

깊이 1부터 탐색해야 하고

방향은 왼쪽, 위쪽, 오른쪽 순으로 탐색해야 한다.

 

한 턴이 끝나면 적들은 한 칸씩 내려와야 하는데

궁수가 한 칸씩 위로 올라가는 게 더 효율적인 구현이 가능하다.

 

궁수 2명 이상이 같은 적을 공격할 수도 있으므로

공격할 적들을 일단 큐에 담아놓고

턴이 끝날 때 attacked에 체크하고

공격한 적의 수는 한 번만 카운트한다.

 

< C++ 코드 >

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int arr[16][16], dx[3] = { 0, -1, 0 }, dy[3] = { -1, 0, 1 }; // 좌, 상, 우 순
int N, M, D, Max, res;
vector <int> archer;

class info {
public:
	int x, y, d;
	info(int x, int y, int d) {
		this->x = x, this->y = y, this->d = d;
	}
};

void Combination(int idx, int cnt) {
	if (cnt == 3) {
		bool attacked[16][16] = { false };
		for (int k = N - 1; k >= 0; k--) { // 궁수 행 위치(맨 밑에서부터 올라옴)
			queue <pair<int, int>> attack;

			for (int t = 0; t < 3; t++) { // 궁수 열 위치(archer에 저장되어 있음)
				bool visited[16][16] = { false }, out = false;
				queue <info> q;
				
				if (arr[k][archer[t]] && !attacked[k][archer[t]]) { // 거리 1에 적이 있을 때
					attack.push(make_pair(k, archer[t]));
					continue;
				}
				else q.push(info(k, archer[t], 1)), visited[k][archer[t]] = true; // 아니라면 BFS 시작

				while (!q.empty()) {
					int X = q.front().x, Y = q.front().y;
					if (q.front().d == D) break; // 탐색해야 하는 부분들이 D의 범위를 벗어나게 되면 끝

					for (int i = 0; i < 3; i++) {
						int x = X + dx[i], y = Y + dy[i];
						if (x < 0 || x >= N || y < 0 || y >= M || visited[x][y]) continue; // 범위를 벗어나거나 방문했었으면 스킵
						if (!visited[x][y]) q.push(info(x, y, q.front().d + 1)), visited[x][y] = true; // BFS
						if (arr[x][y] && !attacked[x][y]) { // 공격 가능한 적
							attack.push(make_pair(x, y)), out = true;
							break;
						}
					}

					if (out) break;
					q.pop();
				}
			}
			while (!attack.empty()) {
				if (!attacked[attack.front().first][attack.front().second]) attacked[attack.front().first][attack.front().second] = true, res++; // 중복 공격 가능하지만 카운트는 한 번임
				attack.pop();
			}
		}
		Max = max(Max, res), res = 0;
		return;
	}
	for (int i = idx; i < M; i++) {
		archer.push_back(i), Combination(i + 1, cnt + 1), archer.pop_back();
	}
}

int main() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> arr[i][j];
	Combination(0, 0);
	cout << Max;
	return 0;
}

 

< JAVA 코드 >

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_17135_캐슬디펜스 {
	private static int N, M, D, res = 0;
	private static int arr[][], arr2[][], archer[] = new int[3];
	private static boolean attacked[][];
	private static Queue <int[]> q = new LinkedList<>();
	
	public static int bfs() {
		for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) arr2[i][j] = arr[i][j]; // 배열 변경할거라서 복사해서 써야 함
		int cnt = 0;
		attacked = new boolean[N][M];
		for(int i = N; i > 0; i--) { // 궁수들이 한 행씩 위로 올라감
			for(int j = 0; j < 3; j++) { // 궁수들의 위치(archer[j] = y좌표)
				boolean clear = false;
				for(int d = 1; d <= D; d++) { // 거리 1부터 D까지 공격 가능
					for(int a = 1; a <= d; a++) { // 왼쪽 방향부터 중앙까지
						int x = i - a, y = archer[j] - (d - a); // 궁수가 가장 먼저 공격할 수 있는 위치
						if(x < 0 || y < 0 || y >= M || arr2[x][y] == 0) continue; // 범위를 벗어나거나 적이 없으면 넘어감
						if(!attacked[x][y]) q.offer(new int[] {x, y}); // 공격한 적 위치 중복되지 않게 담아두기
						attacked[x][y] = true;
						clear = true;
						break;
					} 
					if(clear) break; // 처리하면 다음 궁수 차례로 넘기기
					for(int a = d - 1; a >= 1; a--) { // 오른쪽 방향
						int x = i - a, y = archer[j] + (d - a); // 궁수가 가장 먼저 공격할 수 있는 위치
						if(x < 0 || y < 0 || y >= M || arr2[x][y] == 0) continue; // 범위를 벗어나거나 적이 없으면 넘어감
						if(!attacked[x][y]) q.offer(new int[] {x, y}); // 공격한 적 위치 중복되지 않게 담아두기
						attacked[x][y] = true;
						clear = true;
						break;	
					} 				
					if(clear) break; // 처리하면 다음 궁수 차례로 넘기기
				}	
			}
			cnt += q.size(); // 공격한 적의 수만큼 카운트
			while(!q.isEmpty()) arr2[q.peek()[0]][q.poll()[1]] = 0; // 공격한 적들 0으로 바꿔주기
		}	
		return cnt;
	}
	
	public static void combination(int cnt, int idx) { // 궁수 위치 조합으로 배치하기
		if(cnt == 3) {
			res = Math.max(res, bfs());
			return;
		}
		for(int i = idx; i < M; i++) {
			archer[cnt] = i;
			combination(cnt + 1, i + 1);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt(); D = sc.nextInt();
		arr = new int[N][M]; arr2 = new int[N][M];
		for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) arr[i][j] = sc.nextInt();
		combination(0, 0);
		System.out.println(res);
	}
}