캐슬 디펜스

• 시뮬레이션

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int[][] arr;
	static int N;
	static int M;
	static int T;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		T = sc.nextInt();

		arr = new int[N + 1][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		int[] arrs = new int[M];
		for (int i = 0; i < M; i++) {
			arrs[i] = i;
		}

		c(arrs, 0, 0, new int[3]);
		System.out.println(max);
	}

	static int sum = 0;
	static int max = 0;

	static void c(int[] arrs, int n, int c, int[] re) {
		if (re.length == c) {
			// System.out.println(Arrays.toString(re));
			// 끝줄에 조합값 추가
			int[][] tmp = new int[N + 1][M];

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

			for (int i = 0; i < re.length; i++) {
				tmp[N][re[i]] = 2;
			}
			Queue<Node> q = new LinkedList<>();

			for (int m = 0; m < N; m++) {
				/*for (int i = 0; i < N + 1; i++) {
					System.out.println(Arrays.toString(tmp[i]));
				}*/
				boolean[][] che2 = new boolean[N][M];
				boolean[] che1 = new boolean[M];
				for (int i = 0; i < M; i++) {
					if (tmp[N][i] == 2 && tmp[N - 1][i] == 1) {
						che1[i] = true;
						che2[N - 1][i] = true;
					}
				}
				//System.out.println();
				for (int i = 0; i < M; i++) {
					if (tmp[N][i] == 2 && che1[i] == false) {
						boolean[][] che = new boolean[N + 1][M];
						q.add(new Node(N, i, 0));
						che[N][i] = true;
						while (!q.isEmpty()) {
							Node node = q.poll();
							if (tmp[node.r][node.c] == 1 && node.cnt <= T) {
								che2[node.r][node.c] = true;
								break;
							}
							// 처음시작
							if (node.cnt == 0) {
								int nr = node.r + dr[1];
								int nc = node.c + dc[1];
								if (nr >= 0 && che[nr][nc] == false) {
									q.add(new Node(nr, nc, 1));
									che[nr][nc] = true;
								}
							}
							// 다음
							else {
								for (int k = 0; k < 3; k++) {
									int nr = node.r + dr[k];
									int nc = node.c + dc[k];
									if (nr >= 0 && nc >= 0 && nc < M && che[nr][nc] == false) {
										q.add(new Node(nr, nc, node.cnt + 1));
										che[nr][nc] = true;
									}
								}
							}
						}
						q.clear();
					}
				}
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (che2[i][j] == true) {
							sum++;
							tmp[i][j] = 0;
						}
					}
				}

		/*		for (int i = 0; i < N + 1; i++) {
					System.out.println(Arrays.toString(tmp[i]));
				}*/
	/*			System.out.println();

				System.out.println();
				System.out.println(sum);*/
				for (int i = N - 1; i >= 1; i--) {
					for (int j = 0; j < M; j++) {
						tmp[i][j] = tmp[i - 1][j];
					}
				}
				for (int i = 0; i < M; i++)
					tmp[0][i] = 0;

			}
			// System.out.println(sum);
			if (sum > max)
				max = sum;
			// 출력

			// 끝줄 다시 0으로 초기화

			sum = 0;
			return;
		}
		if (arrs.length == n) {
			return;
		}
		re[c] = arrs[n];
		c(arrs, n + 1, c + 1, re);
		c(arrs, n + 1, c, re);

	}

	static int[] dr = { 0, -1, 0 };
	static int[] dc = { -1, 0, 1 };

	static class Node {
		int r, c, cnt;

		Node(int r, int c, int cnt) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}

}