백준 17135 캐슬 디펜스 (Java)

1. 문제 링크

17135번: 캐슬 디펜스

 

2. 문제 및 입출력예제

3. 문제 풀이

궁수의 조합을 먼저 구하고 그 조합으로 dfs를 진행한다.

사정거리 안에 있는 적을 찾고 비교해서 최솟값을 계속 바꾼다.

최솟값이 있다면 boolean 배열의 값을 true로 한다. (이 배열은 같은 적을 공격할 경우를 대비해서 만들었다.)

모든 궁수가 공격할 적을 찾았다면 기존 배열인 map의 값을 0으로 바꾸고 count를 증가한다.

그러고 한 줄씩 아래로 내리고 count값이 크다면 값을 바꾼다.

다른 조합으로 가기 전에 map을 원래 있는 배열로 바꾸고 이 내용을 반복한다.

 

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M, D, map[][], clone[][], numbers[], die;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nmd = br.readLine().split(" ");
		N = Integer.parseInt(nmd[0]);
		M = Integer.parseInt(nmd[1]);
		D = Integer.parseInt(nmd[2]); // 거리
		map = new int[N][M];
		clone = new int[N][M];
		numbers = new int[3];
		for (int i = 0; i < N; i++) {
			String[] split = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(split[j]);
				clone[i][j] = map[i][j];
			}
		}

		//궁수 조합 먼저
		com(0, 0);
        
		System.out.println(die);
	}

	private static void dfs(int[] bow) {
		int count = 0;

		for (int t = 0; t < N; t++) {
			boolean[][] kill = new boolean[N][M]; // 같은 적을 공격하는 경우

			for (int i = 0; i < 3; i++) {
				int curX = N;
				int curY = bow[i];

				int minDis = Integer.MAX_VALUE;
				int minX = Integer.MAX_VALUE;
				int minY = Integer.MAX_VALUE;

				for (int j = 0; j < N; j++) {
					for (int k = 0; k < M; k++) {
						if (map[j][k] == 1) {
							int dis = Math.abs(j - curX) + Math.abs(k - curY);
							if (dis <= D) {
								if (minDis > dis) {
									minX = j;
									minY = k;
									minDis = dis;
								} 
								else if (minDis == dis && minY > k) {
									minX = j;
									minY = k;
								}
							}

						}

					}
				}
				if (minDis != Integer.MAX_VALUE) {
					kill[minX][minY] = true;
				}

			}

			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 = N - 1; i > 0; 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;
			}
			die = Math.max(die, count);
		}

		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = clone[i][j];
			}
		}
	}

	private static void com(int cnt, int start) {
		if (cnt == 3) {
			dfs(numbers);
			return;
		}
		for (int i = start; i < M; i++) {
			numbers[cnt] = i;
			com(cnt + 1, i + 1);
		}

	}
}