[백준] G5 17135번 캐슬 디펜스 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

17135번: 캐슬 디펜스

[문제] 

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

[입력]

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

[출력]

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

 

---

[풀이]

1. 기존의 입력정보를 담아 둘 map과 해당 map이 변경될 경우 초기화를 해주기 위한 map_copy를 만들어준다.

2. 조합으로 궁수들의 위치를 3개 선택해준다.

3. 3개가 선택이 되면 시뮬레이션을 돌린다.

4. 궁수가 공격을 할 수 있다고 바로 0으로 만들어버리면 동시에 같은 적을 공격하지 않기 때문에 체크만 해둔다.

5. 모든 궁수가 공격할 적의 체크가 끝나면 체크된 적들을 죽였다는 표시로 0으로 변경해주고 count를 증가시켜준다.

6. 적들이 이동을 해야하기 때문에 이동하는 것을 맵에 적용시켜준다.

7. 4~6번을 반복해서 결과값을 max와 비교해서 값을 갱신해준다.

8. 모든 조합의 경우를 탐색하고 최고값을 출력해준다.

[접근]

1. map이 변경된 것을 어떻게 복구시킬까?라고 생각을 해서 map_copy를 이용했다.

2. 3개의 궁수 위치를 어떻게 선택할지 고민했는데 이를 조합으로 선택하였다.

3. 3개의 위치가 정해지면 시뮬레이션을 돌려준다.

4. 바로 0으로 변경시켰는데 조건에 의해서 틀렸다는 것을 인지하고 수정하였다.

[코드]

package BOJ_gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_G4_17135 {
	static int n, m, d;
	static int[][] map;
	static int[][] copy;
	static int count;
	static int max = Integer.MIN_VALUE;
	static ArrayList<int[]> bow;
	static boolean[] archer;
	static int min_dist, min_x, min_y;
	
	public static void main(String[] args) throws Exception {
		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][m];
		copy = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				copy[i][j] = map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		archer = new boolean[m];
		comb(0, 0);
		
		System.out.println(max);
	}
	
	public static void comb(int start, int cnt) {
		if (cnt == 3) {
			bow = new ArrayList<>();
			
			for (int i = 0; i < m; i++) {
				if (archer[i]) {
					bow.add(new int[] {n, i}); // 활잡이 위치 추가
				}
			}
			attack();
			return;
		}
		
		for (int i = start; i < m; i++) {
			if (archer[i]) continue;
			archer[i] = true; // 활잽이가 있는 경우
			comb(i + 1, cnt + 1);
			archer[i] = false; // 없는 경우
		}
	}
	
	public static void attack() {
		count = 0; // 마릿수
		
		// n만큼 == 모든 적들이 성 까지 오면 종료
		for (int t = 0; t < n; t++) {
			boolean[][] kill = new boolean[n][m];
			
			// 각 궁수별로 최소 거리에 있는 몬스터 구하기
			for (int i = 0; i < 3; i++) {
				int cur[] = bow.get(i);
				
				min_dist = Integer.MAX_VALUE; // 최소 거리
				min_x = Integer.MAX_VALUE; // 최소 거리에 있는 몬스터의 x좌표
				min_y = Integer.MAX_VALUE; // 최소 거리에 있는 몬스터의 y좌표
				
				for (int j = 0; j < n; j++) {
					for (int k = 0; k < m; k++) {
						if (map[j][k] == 1) {
							int dist = dist(j, cur[0], k, cur[1]);
							if (min_dist >= dist) {
								if (min_dist > dist) {
									// 최소 거리가 작으면 가까운거 부터 사냥
									min_dist = dist; // 최소거리 변경
									min_x = k; // 최소 거리의 x
									min_y = j; // 최소 거리의 y
								}
								else {
									if (min_x > k) {
										// 거리가 같다면 가장 왼쪽 사냥
										min_x = k; // 최소 거리의 x
										min_y = j; // 최소 거리의 y
									}
								}
							}
						}
					}
				}
				
				// 몬스터를 구했다면 해당 몬스터를 공격해야함
				if (min_dist <= d) {
					kill[min_y][min_x] = true;
				}
				// 여기서 바로 0으로 만들지 않고 true로만 처리해줌
				// why? 바로 처리해버리면 뒤에 활잽이가
				// 똑같은 적을 공격할 수 도 있는데 그 경우를 없애버림
			}
			
			// 활잽이 3마리 다 돌리면
			// 방문된 곳 == 공격할 곳인거 공격
			// 공격한 것 == 처리한 것의 카운트 증가
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (kill[i][j]) {
						map[i][j] = 0;
						count++;
					}
				}
			}
			
			// 성 바로 위에 있는 것 처리
            for (int i = 0; i < m; i++) {
                map[n - 1][i] = 0;
            }
 
            // 적들 한 칸씩 전진
            for (int i = n - 1; i >= 1; i--) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = map[i - 1][j];
                }
            }
            
            // 맨 위에 있는 것 처리
            for (int i = 0; i < m; i++) {
                map[0][i] = 0;
            }
            
            // 가장 많이 처리한 경우로 값 변경
            max = Math.max(max, count);
		}
		
		// 맵 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = copy[i][j];
			}
		}
	}
	
	// 거리 구하기
	public static int dist(int x1, int x2, int y1, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}
}