캐슬 디펜스 [백준 17135][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

17135번: 캐슬 디펜스

DFS나 BFS를 사용했어야 했는데 

깡 시뮬레이션 돌려버렸다. ㅠ

궁수 턴과 몬스터 턴으로 구별하고 Queue를 사용하여 타겟을 정해주었다.

package WorkShop;

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

class Archer{
	int row, col;
	public Archer(int row, int col) {
		this.row = row;
		this.col = col;
	}
}
public class 케슬디펜스 {
	public static boolean[][] visit;
	public static int[][] map;
	public static Queue<Integer> q;
	public static int N,M,D, max;
	public static int MM;
	public static boolean[] V;
	public static int[] varr, archerArr;
	public static int cnt, ans;
	public static int[][] tempmap;
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		
		visit = new boolean[N][M];
		map = new int[N][M];
		V = new boolean[M]; //조합중복방지
		varr = new int[M]; //궁수의 번호
		
		archerArr = new int[3]; //아처배열
		
		for (int i = 0; i < M; i++) varr[i] = i;
			
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) cnt++;
			}
		}
		max = Integer.MIN_VALUE;
		combination(0,0);
		System.out.println(MM);
		
	}
	public static void combination(int start, int cnt) {
		if(cnt == 3) { //3명의 궁수를 뽑았다.
			tempmap = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					tempmap[i][j] = map[i][j];
				}
			}
			max = Math.max(gameStart(archerArr[0],archerArr[1],archerArr[2]), max);
			MM = Math.max(max,MM);
			
			return;
		}
		for (int i = start; i < M ; i++) { // i == start 면서 중복방지
			if(!V[i]) {
				V[i] = true;
				archerArr[cnt] = varr[i]; 
				combination(i,cnt+1);
				V[i] = false;
			}
		}
	}
	
	public static int gameStart(int a1, int a2, int a3) {
		int monsterNum = cnt;
		ans = 0;
		Archer[] archer = new Archer[3];
		archer[0] = new Archer(N, a1);
		archer[1] = new Archer(N, a2);
		archer[2] = new Archer(N, a3);
		
		//아처 1 ,2 ,3
		while(true) {
			//궁수 턴
			Queue<int[]> target = new LinkedList<>(); //공격할놈
			
			for (int i = 0; i < 3; i++) { //궁수 3명
				
				Queue<int[]> q = new LinkedList<>(); 
				int distance=Integer.MAX_VALUE;
				for (int j =N-1; j >= 0; j--) {
					for (int k = 0; k < M; k++) {
						if(tempmap[j][k] != 1) continue;
						distance = Integer.min(Math.abs(archer[i].row - j) + 
								Math.abs(archer[i].col - k), distance);
					}
				}
				for (int j =N-1; j >= 0; j--) {
					for (int k = 0; k < M; k++)  {
						if(tempmap[j][k] == 1 && distance <= D && ((Math.abs(archer[i].row - j) + 
								Math.abs(archer[i].col - k)) == distance)) {
								q.add(new int[] {j,k});
								
						}
					}
				}
				
				if(distance == Integer.MAX_VALUE) continue;
				//궁수가 사격할 수 있는 몬스터
				int size = q.size();
				int minrow = 0, mincol = Integer.MAX_VALUE;
				for (int j = 0; j < size; j++) {
					int[] arr = q.poll();
					if(arr[1] <= mincol) {
						minrow = arr[0];
						mincol = arr[1];
					}
				}
				if(mincol == Integer.MAX_VALUE) continue;
				//첫번째~3번째 궁수까지 사격할 수 있는 몬스터 넣기
				target.add(new int[] {minrow, mincol});
			}
			
			int size = target.size();
			for (int i = 0; i < size; i++) {
				int[] arr = target.poll();
				if(tempmap[arr[0]][arr[1]] == 1) {
					tempmap[arr[0]][arr[1]] = 0;
					ans++;
					monsterNum--;
				}
			}
			
			//몬스터 턴
			for (int i = N - 1; i >= 0; i--) {
				for (int j = M - 1; j >= 0; j--) {
					if(tempmap[i][j] == 1) {
						int nx = i + 1; 
						tempmap[i][j] = 0; //몬스터를 위치 이동
						
						if(nx<N) { //몬스터의 다음 경로가 맵안에 있다면
							tempmap[nx][j] = 1; 
						}
						else {
							monsterNum--;
						}
					}
				}
			}
			if(monsterNum == 0) break;
		}
		
		return ans;
	}
	
}