백준_17135_캐슬디펜스

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

17135번: 캐슬 디펜스

궁수에 위치를 선정해주고 선정이 된 이후에 시물레이션을 통해 적을 최대로 처지 할 수 있는 수의 최댓값을 구하는 문제이다. 

 

일단 배열에 세로 열 부분에 궁수를 배치 할 수 있는데 최대 세명까지 배치할 수 있으므로 백트래킹으로 궁수에 위치를 먼저 선점해야 한다.  3명이 된이후에는 원래의 배열을 복사하여 시물레이션을 진행한다.  원래의 배열을 복사하는 이유는 궁수의 배치가 달라질 때마다 시뮬레이션을 진행해야 하기 때문이다.

static void dfs(int index, int count) {
		if(count == 3) {
			int[][] copy = new int[n + 1][m + 1];
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= m; j++) {
					copy[i][j] = map[i][j];
				}
			}
			ans = Math.max(ans, game(copy));
			return;
		}
		for(int i = index; i <= m; i++) {
			if(!check[i]) {
				check[i] = true;
				dfs(index + 1, count + 1);
				check[i] = false;
			}
		}
	}

 

궁수가 배치됐다면 시물레이션을 진행한다. 일단 각 궁수 기준으로 모든 적지점에 좌표와 거리를 검사하여 문제에서 주어진 거리 이하라면 공격할 수 있기 때문에 적 리스트 객체 배열을 만들어줘서 여기에 넣어준다. 왜냐하면 한 궁수가 공격할 수 있는 적은 가장 가까운 적인데 거리가 같다면 왼쪽에 있는 적을 공격해야 하기 때문이다.(정렬로 해결)

 

한 궁수를  탐색한 후 이궁수가 공격할 수 있는 적들이 있다면 이 중에서 가장 가깝고 왼쪽에 있는 적에 위치 값을 1이 아닌 2로 바꾸어준다. (바로 삭제하지 않는 이유는 다른 궁수도 이적을 공격할 수 있기 때문이다. 문제에서 한적은 여러 궁수의 공격을 받을 수 있다 했음)

모든 궁수가 위와 같은 과정을 진행했다면 이제 좌표가 2 인적은 제거해주고 나머지 적들은 아래로 한 칸씩 이동해준다.

 

위 과정을 모든 적이 죽거나 격자판 내에 적들이 없다면 종료한다.

 

 

 

static int game(int[][] copy) {
		int count = 0;
		while(true) {
        // 적들이 모두 죽거나 좌표에 적이없으면 종료한다.
			if(EnemyAllDead(copy)) {
				break;
			}
            
			for(int i = 1; i <= m; i++) {
				ArrayList<Point> enemy = new ArrayList<>();
                // 궁수가 있는 지역일떄 진행
				if(check[i]) {
					for(int j = 1; j <= n; j++) {
						for(int k = 1; k <= m; k++) {
                        	//적이있는 좌표일떄
							if(copy[j][k] > 0) {
								int distance = Math.abs((n + 1) - j) + Math.abs(i - k);
								//만약 거리가 주어진 거리이하이면 리스트에 추가(제거될 적 후보들이라고 생각)
                                if(distance <= d) {
									enemy.add(new Point(j, k, distance));
								}
							}
						}
					}
				}
				// 만약 제거될 적들이 존재한다면 정렬을 통해 이중 거리가 가장 가깝고 왼쪽에있는 적의 좌표를 2로 바꿈
				if(enemy.size() > 0) {
					Collections.sort(enemy);
					copy[enemy.get(0).x][enemy.get(0).y] = 2;
				}
			}
			
            // 모든궁수에대하여 위과정이 끝났으면 2인 좌표는 삭제하고(적을제거) 나머지 적들은 아래로 한칸 이동한다.
			for(int i = n; i >= 1; i--) {
				for(int j = 1; j <= m; j++) {
					if(copy[i][j] == 2) {
						copy[i][j] = 0;
						count++;
					}else if(copy[i][j] == 1) {
						int new_x = i + 1;
						copy[i][j] = 0;
						if(new_x <= n) {
							copy[new_x][j] = 1;
						}
					}
				}
			}
		}
		return count;

 

클래스를 정렬하는 부분은 많이 쓰이기 때문에 알아두면 유용하다. 

이후 ArrayList <Point> enemy = new ArrayList <>();  Collections.sort(enemy)  Point 형 객체 배열을 선언하고 값들을 넣어준 후 정렬 매소드를 실행하면 거리가 가까운 순 거리가 가깝다면 y 좌표가 작은 순으로 정렬된다.

		     // 정렬하기위해서 선언해줘야하는 부분
class Point implements Comparable<Point>{
	int x;
	int y;
	int d;
	public Point(int x, int y, int d) {
		this.x = x;
		this.y = y;
		this.d = d;
	}
	@Override
	public int compareTo(Point o) {
    	// 만약 거리가 같다면 y 좌표가 적은순으로 정렬
		if(this.d == o.d) {
			return this.y - o.y;
		}
        // 거리가 다르다면 거리가 가까운 순으로 정렬
		return this.d - o.d;
	}
	
}

 

 

다음은 전체 코드이다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Bj_17135 {
	
	static int[][] map;
	static int n, m, d;
	static int ans = 0;
	static boolean check[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		d = sc.nextInt();
		map = new int[n + 1][m + 1];
		check = new boolean[m + 1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		dfs(1, 0);
		System.out.println(ans);
}
	
	static void dfs(int index, int count) {
		if(count == 3) {
			int[][] copy = new int[n + 1][m + 1];
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= m; j++) {
					copy[i][j] = map[i][j];
				}
			}
			ans = Math.max(ans, game(copy));
			return;
		}
		for(int i = index; i <= m; i++) {
			if(!check[i]) {
				check[i] = true;
				dfs(index + 1, count + 1);
				check[i] = false;
			}
		}
	}
	static int game(int[][] copy) {
		int count = 0;
		while(true) {
			if(EnemyAllDead(copy)) {
				break;
			}
			for(int i = 1; i <= m; i++) {
				ArrayList<Point> enemy = new ArrayList<>();
				if(check[i]) {
					for(int j = 1; j <= n; j++) {
						for(int k = 1; k <= m; k++) {
							if(copy[j][k] > 0) {
								int distance = Math.abs((n + 1) - j) + Math.abs(i - k);
								if(distance <= d) {
									enemy.add(new Point(j, k, distance));
								}
							}
						}
					}
				}
				
				if(enemy.size() > 0) {
					Collections.sort(enemy);
					copy[enemy.get(0).x][enemy.get(0).y] = 2;
				}
			}
			
			for(int i = n; i >= 1; i--) {
				for(int j = 1; j <= m; j++) {
					if(copy[i][j] == 2) {
						copy[i][j] = 0;
						count++;
					}else if(copy[i][j] == 1) {
						int new_x = i + 1;
						copy[i][j] = 0;
						if(new_x <= n) {
							copy[new_x][j] = 1;
						}
					}
				}
			}
		}
		return count;
	}
	static boolean EnemyAllDead(int[][] copy) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(copy[i][j] != 0) {
					return false;
				}
			}
		}
		return true;
	}
	}

class Point implements Comparable<Point>{
	int x;
	int y;
	int d;
	public Point(int x, int y, int d) {
		this.x = x;
		this.y = y;
		this.d = d;
	}
	@Override
	public int compareTo(Point o) {
		if(this.d == o.d) {
			return this.y - o.y;
		}
		return this.d - o.d;
	}
	
}