[BOJ 17135] 캐슬 디펜스

 

1. 궁수 3명을 각 행의 m열에 3명을 배치시킬 수 있다, --> mC3의 경우의 수로 궁수를 배치

 

2. 궁수가 공격할 수 있는 적은 거리가 D이하인 적에서 가장 가까운 적, 그러한 적이 여러명이면 가장 왼쪽에 있는 적을 우선적으로 쏜다.

    * 즉, 왼쪽 -> 위 -> 오른쪽 순으로 탐색(BFS)하여 제일 먼저 만나는 적이 가장 가까운 적이다.

    * 최우선으로 가까운 적은 궁수 바로 위에 위치하는 적이므로 시작점(궁수의 바로 위 지점)을 큐에 넣고 탐색 시작

 

3. 궁수는 동시에 공격하며 같은 적을 공격할 수 있다

    * 3명의 궁수가 공격할 수 있는 가장 가까운 적을 3명이 모두 선택하고 나서 적을 죽여야 한다. 

    * 1명이 적 선택하고 바로 죽이고 다른 1명이 적 선택하고.. 안된다는 것.  

 

4. 궁수의 공격이 끝나면 적이 1칸씩 성으로 이동한다

    * 거꾸로 생각해서 궁수의 위치를 1칸씩 위로 옮기면 적들을 옮기지 않아도 된다.

 

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

public class Main {

	static int[][] original; // 원본 배열 
	static int n,m,d; // 행, 열, 궁수의 사격거리
	static int[] placeArcher = new int[3]; // 궁수 배치시키기 위한 배열
	static int ans = 0;

	static int[] Xarr = {0,-1,0};
	static int[] Yarr = {-1,0,1};
	
	static class Enemy{
		
		int x;
		int y;
		
		public Enemy(int x, int y) {
			
			this.x=x;
			this.y=y;
		}

	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		String[] input = br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		m = Integer.parseInt(input[1]);
		d = Integer.parseInt(input[2]);
		original = new int [n+1][m];
		
		for (int i=0; i< n; i++) {
			input = br.readLine().split(" ");
			for (int j=0; j<m; j++) {
				original[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		Combination(0,0); // 궁수 배치시키는 방법을 조합으로 구한다
		
		sb.append(ans);
		wr.write(sb.toString());
		wr.close();
		br.close();
	}
	
	private static void Combination(int start, int cnt) {
		
		if (cnt == 3) {
			Attack();
			return;
		}
		
		for (int i= start; i < m; i++) {
			placeArcher[cnt] = i;
			Combination(i+1, cnt+1);
		}
		
		
	}
	private static void Attack() {
		
		// 1. 배열 복사
		int[][] copyArr = new int [n+1][m];
	
		for (int i=0; i<n; i++) {
			for (int j=0; j<m; j++) 
				copyArr[i][j] = original[i][j];
		}
		
		// 2. 계산 로직 시작
		int killCount = 0;
		
		List<Enemy> list= new ArrayList<>();
		
		for (int i=n-1; i>=0; i--) { // 맨 아래에서부터
			
			for (int archer = 0; archer < 3; archer++) { // 각각의 archer가
				Enemy temp = Dead(i,placeArcher[archer],copyArr); // 가장 가까운 적을 찾으러 가보는데
				if (temp == null) continue; // 없으면 상관없다.
				
				list.add(temp); // 죽일 수 있는 적이 있었다면 add
			}
			
			for (int j=0; j<list.size(); j++) { // 추가된 적의 개수 만큼
				
				int x = list.get(j).x;
				int y = list.get(j).y;
				
				if (copyArr[x][y] == 1) { // 살아있는 적, 중복이 있었다 하더라도 
					killCount++; // 최초만 killCount++
					copyArr[x][y] = 0;
				}
			}
			
		}
		
		ans = Math.max(ans, killCount);
		
	}
	private static Enemy Dead(int x, int y, int[][] copyArr) {
		
		Queue<Enemy> q = new ArrayDeque<>();
		boolean[][] visited = new boolean[n][m];
		
		q.add(new Enemy(x,y));
		Enemy temp;
		int nx,ny;
		while(!q.isEmpty()) {
			
			temp = q.poll();
			
			if(visited[temp.x][temp.y]) continue;
			
			if(copyArr[temp.x][temp.y] == 1) {
				return temp;
			}
			
			visited[temp.x][temp.y] = true;
			
			for (int i=0; i<3; i++) { // 왼쪽 위 오른쪽 탐색으로 문제 조건에 의해 왼쪽부터 훑을 수 있도록 bfs탐색이다.
				nx = temp.x + Xarr[i];
				ny = temp.y + Yarr[i];
				if (isIn(nx,ny) && CalculateDist(x+1, y, nx, ny)) {
					q.add(new Enemy(nx,ny));
				}
			}
		}
		
		return null;
	}

	private static boolean isIn(int nx, int ny) {
		
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) return false;
		
		return true;
	}

	private static boolean CalculateDist(int archerRow, int archerCol, int enemyRow, int enemyCol) {
		
		int dist = Math.abs(archerRow - enemyRow) + Math.abs(archerCol - enemyCol);
		
		if (dist <= d) {
			return true;
		}
		
		return false;
	}
	


}