[백준] 17135 - 캐슬 디펜스 (자바 Java)

[Gold III] 캐슬 디펜스 - 17135

문제 링크

성능 요약

메모리: 32012 KB, 시간: 312 ms

분류

브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 구현(implementation), 시뮬레이션(simulation)

문제 설명

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

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

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

격자판의 두 위치 (r₁, c₁), (r₂, c₂)의 거리는 |r₁-r₂| + |c₁-c₂|이다.

입력

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

출력

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

---

풀이

문제를 잘 읽자..

궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.

이 조건을 고려하지 않아서 16%쯤에서 계속 틀렸다

조건 고려 잘 하기 ....

---

조합으로 궁수의 가능한 위치를 고르고, game을 진행했다.

game은 맨 위의 row가 맨 아래에 올때까지 N번 진행하였다.

궁수는 화살을 동시에 쏘아야 하기 때문에 미리 거리가 가장 가까운 좌표를 저장해두고, 궁수 3개를 모두 체크한 후에 한꺼번에 쏘도록 했다.

그리고 쏘는 과정에서 배열의 값들이 변하기 때문에 게임 전에 미리 배열의 값을 복사해야 한다

package BOJ.Gold.g3;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ_17135_캐슬디펜스 {

	static int N, M, D;
	static int[][] map;
	static int[] pick;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		D = sc.nextInt();
		map = new int[N][M];
		pick = new int[3];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				map[i][j] = sc.nextInt();

		comb(0, 0);
		System.out.println(ans);
	}

	static void comb(int depth, int start) {
		if (depth == 3) {
			int[][] copy = new int[N][M];
			for (int i = 0; i < N; i++)
				copy[i] = map[i].clone();

			game(0, 0);
			for (int i = 0; i < N; i++)
				map[i] = copy[i].clone();
			return;
		}
		for (int i = start; i < M; i++) {
			pick[depth] = i;
			comb(depth + 1, i + 1);
		}

	}

	static void game(int depth, int cnt) {
		// 게임 한번마다 궁수 3명이 하나씩 쏘기, 한 줄씩 내려오기 게임은 n번 진행하면 됨
		if (depth == N) {
			ans = Math.max(cnt, ans);
			return;
		}

		int[][] minIdx = new int[3][2];
		for (int i = 0; i < 3; i++)
			Arrays.fill(minIdx[i], -1);
		for (int i = 0; i < 3; i++) {
			int r = N;
			int c = pick[i];
			int min = Integer.MAX_VALUE;
			for (int j = depth; j < N; j++)
				for (int k = 0; k < M; k++) {
					if (map[j][k] == 1) {
						int tmp = Math.abs(r - j) + Math.abs(c - k);
						if (tmp <= D && min > tmp) {
							min = tmp;
							minIdx[i][0] = j;
							minIdx[i][1] = k;
						}
						if (min == tmp && minIdx[i][1] > k) {
							minIdx[i][0] = j;
							minIdx[i][1] = k; // 가장 왼쪽
						}
					}
				}
			// 쏘는 건 동시에
		}

		// 쏘기
		for (int i = 0; i < 3; i++)
			if (minIdx[i][0] != -1 && map[minIdx[i][0]][minIdx[i][1]] == 1) {
				map[minIdx[i][0]][minIdx[i][1]] = 0;
				cnt++;
			}

		// 한줄씩 밑으로 이동하기
		for (int n = N - 1; n > 0; n--) {
			map[n] = map[n - 1].clone();
		}
		Arrays.fill(map[0], 0);
		game(depth + 1, cnt);

	}

}