17135. 캐슬디펜스

- 문제를 잘 읽자!! 오늘도 깨달음..!!

- 주석으로 설명을 대신한다.

- 최소 거리를 구하는게 핵심~!

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

public class B_17135_캐슬디펜스2 {

	static int result = Integer.MIN_VALUE;
	static int count;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());
		int[][] arr = new int[N][M];
		int[] posit = new int[3]; // 궁수의 위치
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		comb(0, 0, posit, N, M, D, arr);

		// 결과출력
		System.out.println(sb.append(result));
	}

	// 궁수의 위치 - 조합
	private static void comb(int cnt, int start, int[] posit, int N, int M, int D, int[][] arr) {
		if (cnt == 3) {
			count = 0; // 초기화
			game(posit, arr, N, M, D);
			// 적의 최댓값 갱신
			result = Math.max(result, count);
			return;
		}
		for (int i = start; i < M; i++) { // 열만큼의 위치
			posit[cnt] = i;
			comb(cnt + 1, i + 1, posit, N, M, D, arr);
		}
	}

	// 조합만큼 진행
	private static void game(int[] posit, int[][] arr, int N, int M, int D) {
		// 배열을 복사
		int[][] copy = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copy[i][j] = arr[i][j];
			}
		}

		// 행만큼 게임 진행
		for (int i = 0; i < N; i++) {
			attack(posit, copy, N, M, D);
		}

	}

	// 최적의 적을 찾는다
	private static void attack(int[] posit, int[][] copy, int N, int M, int D) {
		// 최적 위치에 존재하는 적을 체크하기 위함
		boolean[][] check = new boolean[N][M];

		for (int i = 0; i < 3; i++) {
			int now = posit[i];
			int my = -1, mx = -1;
			int min = Integer.MAX_VALUE;

			int H = N - D >= 0 ? N - D : 0; // 확인해 볼 세로의 길이
			for (int j = N - 1; j >= H; j--) {
				for (int k = 0; k < M; k++) {
					if (copy[j][k] == 1) { // 적이 존재하면
						int dist = Math.abs(N - j) + Math.abs(now - k);
						if (dist > D) // 거리가 D를 넘으면 패스
							continue;
						if (dist < min) { // 거리 최소
							min = dist;
							my = j;
							mx = k;
						} else if (dist == min && mx > k) { // 거리가 같을 때 더 왼쪽에 위치하면
							my = j;
							mx = k;
						}
					}
				}
			}
			// 최적 위치에 존재하는 적을 찾음
			if (my != -1) {
				check[my][mx] = true;
			}
		}

		// 지도 변경
		changeMap(N, M, check, copy);
	}

	// 다음 연산을 위해 지도 재정렬
	private static void changeMap(int N, int M, boolean[][] check, int[][] copy) {
		// 적을 없애기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (check[i][j]) {
					copy[i][j] = 0;
					count++;
				}
			}
		}

		// 적들을 내려보내기
		for (int i = N - 2; i >= 0; i--) {
			for (int j = 0; j < M; j++) {
				copy[i + 1][j] = copy[i][j];
			}
		}
		// 맨윗줄은 0으로
		for (int i = 0; i < M; i++) {
			copy[0][i] = 0;
		}

	}
}