[백준, BOJ 17135] 캐슬 디펜스 (java)

728x90

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

17135번: 캐슬 디펜스

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

www.acmicpc.net

문제

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

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

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

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

입력

출력

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

제한

3 ≤ N, M ≤ 15
1 ≤ D ≤ 10

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

예제 출력 5

예제 입력 6

예제 출력 6

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

public class Main {
	
	static int N;
	static int M;
	static int D;
	static int[][] graph;
	static int[][] copyGraph;
	static int[] archer = new int[3];
	static int result = 0;
	
	private static void down() { // 적들이 아래로 한 칸 씩 이동하는 메소드
		for (int i = N - 1; i > 0; i--) {
			copyGraph[i] = copyGraph[i - 1];
		}
		copyGraph[0] = new int[M];
	}
	
	private static int[] attack(int y) { // y 위치에 있는 궁수가 공격할 적의 인덱스를 반환하는 메소드
		for (int i = 1; i <= D; i++) { // 가장 가까운 적부터
			for (int j = -i; j <= i; j++) { // 거리가 같다면 왼쪽부터
				int ny = y + j;
				int nx = N - i + Math.abs(j);
				if(nx >= 0 && nx < N && ny >= 0 && ny < M && copyGraph[nx][ny] == 1) {
					return new int[] {nx, ny};
				}
			}
		}
		return null;
	}
	
	private static void play() { // 궁수 3명이 N턴의 게임을 진행한다.
		int[][] enemy = new int[3][2]; // 공격할 적의 위치
		int count = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 3; j++) { // 궁수 3명이 공격할 적들의 위치를 구한다.
				enemy[j] = attack(archer[j]);
			}
			for (int j = 0; j < 3; j++) { // 한 명씩 공격
				if(enemy[j] != null && copyGraph[enemy[j][0]][enemy[j][1]] == 1) { // 공격할 적이 없거나 이미 적이 죽은 경우가 아니면
					copyGraph[enemy[j][0]][enemy[j][1]] = 0; // 적을 죽이고
					count++; // 죽인 적의 수 카운트
				}
			} // 궁수 공격 끝
			down(); // 적들 한 칸 이동
		} // 적들이 N번 아래로 내려오면 게임 끝남
		
		result = Math.max(result, count); // 현재 궁수의 위치가 가장 많은 적을 죽였다면 result 갱신
	}
	
	private static void pick(int n, int i) { // 궁수 3명의 자리를 고르는 메소드
		if(n == 3) { // 궁수 3명 다 골랐다면
			// graph deep copy
			copyGraph = new int[N][M];
			for (int j = 0; j < N; j++) {
				copyGraph[j] = graph[j].clone();
			}
			play(); // 게임 시작
			return;
		}
		
		for (int j = i; j < M; j++) {
			archer[n] = j;
			pick(n + 1, j + 1);
		}
	}

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 행의 수 N, 열의 수 M, 공격 거리 제한 D 입력
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		
		// 격자판 상태 입력
		graph = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 궁수 3명 골라서 게임해본 뒤 최대값 구하기
		pick(0, 0);
		
		// 출력
		System.out.println(result);
	}

}