[백준][자바][17135]캐슬디펜스

1. 궁수의 위치를 dfs 세팅함 

2. 궁수 위치가 세팅되면  적들과의 distance를 재서 죽일수 있는 적들을 찾아둠

3. 적들 죽이고 카운트

4. 적이동

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Archer {
	int y;
	int x;

	Archer(int y, int x) {
		this.y = y;
		this.x = x;
	}
}

class Enemy implements Comparable {
	int y;
	int x;
	int distance;

	Enemy(int y, int x, int distance) {
		this.y = y;
		this.x = x;
		this.distance = distance;
	}

	// 제일 왼쪽
	// 그중에서도
	@Override
	public int compareTo(Enemy target) {
		if (this.distance < target.distance) { //거리가 크면
			return -1;
		} 
		else if (this.distance > target.distance) {
			return 1;
		} 
		else { // 같은 경우 
			if (this.x < target.x) { 
				return -1; 
			}
			else if (this.x == target.x) {
				return 0; 
			}
			else {
				return 1;
			}
		}
	}

}

public class Main_backjoon_17135_캐슬디펜스 {
	static int ANSWER = 0;
	static int N;
	static int M;
	static int D;
	static int[][] MAP;
	static boolean[] VISITED;
	static Queue qe = new LinkedList();
	static Queue q = new LinkedList();
	static PriorityQueue pqe = new PriorityQueue(); 
	public static void main(String[] args) throws IOException {
		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());
		MAP = new int[N + 1][M];
		VISITED = new boolean[M];
		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());
			}
		}
		setPosition(0,0);
		System.out.println(ANSWER);
	}

	public static Integer calDistance(int y1, int x1, int y2, int x2) {
		int distance = Math.abs(y1 - y2) + Math.abs(x1 - x2);
		return distance;
	}
	
	public static int findEnemy() {
		int count = 0;
		//맵 복사 
		for(int i= 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if (MAP[i][j] == 1) {
					qe.add(new Enemy(i, j, 0));
				}
			}
		}
		
		while(!qe.isEmpty()) {
			int[][] TEMPENEMY  = new int[N][M];
			
			LinkedList list = new LinkedList();
			//1. 적 찾기 		
			for(Archer archar : q) {
				for(Enemy enemy : qe) {
					int r = enemy.y;
					int c = enemy.x;
					int distance = calDistance(r, c, archar.y, archar.x);
					if ( distance <= D ) {
						pqe.add(new Enemy(r,c,distance));
					}
				}

				//가장 거리가 가깝고 제일 왼쪽에 있는 적 꺼내기 
				if(!pqe.isEmpty()) {
					Enemy enemy = pqe.poll();
					list.add(new Enemy(enemy.y, enemy.x, enemy.distance)); //죽일 enemy 들 
					pqe.clear(); 
				}
			}
			
			//한개만 새기 
			for(int i = 0; i < list.size(); i++ ) {
				Enemy e = list.get(i);
				TEMPENEMY[e.y][e.x] += 1;
				if( TEMPENEMY[e.y][e.x] == 1) {
					count += 1;
				}
			}

			//아까 뺸애들 죽여
			int qsize = qe.size();
			for(int s = 0; s < qsize; s++) {
				Enemy e = qe.poll();
				boolean flag = false;
				for(Enemy enemy : list) {
					// 같은게 있으면 
					if(enemy.y == e.y && enemy.x ==  e.x ) { 
						flag = true;
					}
				}
				if(!flag) {
					qe.add(e);
				}
			}
			//enemy move;
			move();
		}
		return count;
	}

	
	/* 만약에 다음 라인에 성에 도착했다면 */
	public static boolean isRange(int yy) {
		if (yy == N) {
			return true;
		} else {
			return false;
		}
	}
	// 3.enemy move;
	public static void move() {
		int qsize = qe.size();
		for(int s = 0; s < qsize; s++) {
			Enemy enemy = qe.poll();
			//무조건 바로 밑으로 하강 
			int yy = enemy.y + 1;
			int xx = enemy.x;
			int distance = enemy.distance;
			if(isRange(yy)) { // 삭제 
				continue;
			}else {
				qe.add(new Enemy(yy,xx, distance));
			}
		}
	}
	
	
	
	// 1. 궁수의 자리를 배치한다
	public static void setPosition(int depth, int start ) {
		// 궁수 배치
		if (depth == 3) {
			// Archer 배치
			for(int i = 0; i < M; i++) {
				if(VISITED[i]) {
					q.add(new Archer(N, i));
				}
			}
			int tempAnswer = findEnemy();
			ANSWER = Math.max(ANSWER, tempAnswer);
			q.clear();
			return;
		}

		for (int i = start; i < M; i++) {
			if (!VISITED[i]) {
				VISITED[i] = true;
				setPosition(depth + 1, i);
				VISITED[i] = false;
			}
		}

	}

}