[백준] 17135: 캐슬 디펜스 문제 풀이

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

문제 접근

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, D, kill, ans;
	static int [][] arr, newArr;
	static int b [] = new int [3];
	static int [] dy = {0, -1, 0};
	static int [] dx = {-1, 0, 1};
	static boolean [][]v;
	
	static void round() {
		List<int []> kills = new ArrayList<>();
		for (int i : b) { // 궁수 3명 반복
			ArrayDeque<int []> q = new ArrayDeque<>();
			v = new boolean[N+1][M]; // 방문 여부 초기화
			q.offer(new int[] {N, i, 0});
			while (!q.isEmpty()) {
				int cur[] = q.poll();
				int y = cur[0];
				int x = cur[1];
				if (newArr[y][x] == 1) { // 적이 궁수의 사정거리 안에 있으면
					kills.add(new int [] {y,x}); // kills list에 추가하고 break;
					break;
				}
				if (cur[2] == D) continue; // 사정거리보다 많이 갔을 경우 탐색하지 않음
				for (int d = 0; d < 3; d++) {
					int ny = y+dy[d];
					int nx = x+dx[d];
					if (0<=ny&&ny<N&&0<=nx&&nx<M&&!v[ny][nx]) {
						v[ny][nx] = true;
						q.offer(new int[] {ny,nx, cur[2]+1});
					}
				}
			}
		}
		for (int e[]:kills) { // kills 리스트에 적재된 적 게임에서 제외
			int y = e[0], x = e[1];
			if (newArr[y][x] == 1) { // 같은 궁수가 하나의 적을 공격하는 경우가 있으므로
				newArr[y][x] = 0; // kill이 중첩되어 올라가는 것을 방지
				kill++; 
			}
		}
	}
	
	static boolean able() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) 
				if (newArr[i][j] == 1) return true;
		return false;
	}
	
	static boolean enemyMove() {
		for (int i = N-1; i > 0; i--)
			for (int j = 0; j < M; j++)
				newArr[i][j] = newArr[i-1][j];

		for (int j = 0; j < M; j++) newArr[0][j] = 0;
		return true;
	}
	
	static void comb(int cnt, int idx) {
		if (cnt == 3) {
			newArr = new int [N+1][M];
			for (int i=0; i<N; i++) newArr[i]=Arrays.copyOf(arr[i], M);
			kill = 0;
			while (able()) {
				round();
				enemyMove();
			}
			ans = Math.max(ans, kill);
			return;
		}
		for (int i=idx; i<M; i++) {
			b[cnt] = i;
			comb(cnt+1, i+1);
		}
	}
	
	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());
		arr = new int [N+1][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) arr[i][j] = Integer.parseInt(st.nextToken());
		}
		comb(0, 0);
		System.out.println(ans);
		br.close();
	}
}