[골드 3] 캐슬 디펜스

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

17135번: 캐슬 디펜스

중간에 개 절었음

 

1. 0 ~ j-1 중에 3개 조합으로 뽑아 (궁수가 놓일 자리임)

2. 각 조합마다 시뮬레이션을 돌려

2-1. 세로번 돌려

2-1-1. 1 궁수에 1적 찾아

2-1-2. 적 실제로 죽이고 kill++

2-1-3. 배열 밑으로 밀기

3. 시뮬 값 answer와 업데이트

 

개 절은 곳

while (!queue.isEmpty()) {
    Point tmp = queue.remove();

    if (Math.abs(arr.length - tmp.y) + Math.abs(j - tmp.x) > D)
        break;

    if (arr[tmp.y][tmp.x] == 1)
        return tmp;

거리 체크 하는 곳을 위에 써야 하는데 return tmp 보다 아래에 써서

거리가 안되는데 찾은 경우도 kill을 해버림

 

* bfs는 같은 depth를 전부 탐색한 뒤에 depth+1을 탐색하기 때문에 굳이 pQ로 안 만들어도 된다.

* 왼쪽 위 오른쪽 이렇게 queue에 넣으면 같은 depth 기준 왼쪽 위 오른쪽 잘 탐색함

 

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

class Point {
	int y, x;

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

public class Main {

	public static int answer = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int N, M, D;
		int[][] arr;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		arr = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		/////////////////////////////////////////////////////

		// 조합으로 n개 중에 3개 뽑아 궁수 배치 해
		boolean[] visited = new boolean[arr[0].length];
		combination(arr, visited, 0, -1, D);
		System.out.println(answer);

	}

	public static void combination(int[][] arr, boolean[] visited, int depth, int last_pick, int D) {
		if (depth == 3) {

			int[][] new_arr = new int[arr.length][arr[0].length];
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr[0].length; j++) {
					new_arr[i][j] = arr[i][j];
				}
			}

			answer = Math.max(answer, simulation(new_arr, visited, D));
			return;
		}

		for (int i = last_pick + 1; i < visited.length; i++) {
			visited[i] = true;
			combination(arr, visited, depth + 1, i, D);
			visited[i] = false;
		}
	}

	public static int simulation(int[][] arr, boolean[] visited, int D) {
		int kill = 0;

		// arr.length번 돌기
		for (int time = 0; time < arr.length; time++) {
			// 공격 후 적이동
			ArrayList<Point> enemies = new ArrayList<>();

			// 사람 돌며 적 찾기
			for (int j = 0; j < visited.length; j++) {
				if (visited[j]) {
					enemies.add(find_enemy(arr, D, j));
				}
			}

			for (Point enemy : enemies) {
				if (enemy != null && arr[enemy.y][enemy.x] == 1) {
					arr[enemy.y][enemy.x] = 0;
					kill++;
				}
			}

			for (int i = arr.length - 1; i > 0; i--) {
				for (int j = 0; j < arr[0].length; j++) {
					arr[i][j] = arr[i - 1][j];
				}
			}

			for (int j = 0; j < arr[0].length; j++) {
				arr[0][j] = 0;
			}

		}

		return kill;
	}

	public static Point find_enemy(int[][] arr, int D, int j) {

		Queue<Point> queue = new LinkedList<>();
		boolean[][] visited = new boolean[arr.length][arr[0].length];

		queue.add(new Point(arr.length - 1, j));
		visited[arr.length - 1][j] = true;

		while (!queue.isEmpty()) {
			Point tmp = queue.remove();

			if (Math.abs(arr.length - tmp.y) + Math.abs(j - tmp.x) > D)
				break;

			if (arr[tmp.y][tmp.x] == 1)
				return tmp;

			// 왼쪽
			if (tmp.x - 1 >= 0 && !visited[tmp.y][tmp.x - 1]) {
				visited[tmp.y][tmp.x - 1] = true;
				queue.add(new Point(tmp.y, tmp.x - 1));
			}

			// 위
			if (tmp.y - 1 >= 0 && !visited[tmp.y - 1][tmp.x]) {
				visited[tmp.y - 1][tmp.x] = true;
				queue.add(new Point(tmp.y - 1, tmp.x));
			}

			// 오른쪽
			if (tmp.x + 1 < arr[0].length && !visited[tmp.y][tmp.x + 1]) {
				visited[tmp.y][tmp.x + 1] = true;
				queue.add(new Point(tmp.y, tmp.x + 1));
			}

		}

		return null;

	}
}