백준 17135 캐슬 디펜스(구현, 조합, BFS) ★★

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

17135번: 캐슬 디펜스

단순 구현 문제인 줄 알고 쉽게 접근했지만 다양한 알고리즘을 사용해야 했던 문제였다.

1. 궁수의 위치를 정해야 하기 때문에 Combination 사용

2. 궁수가 공격을 해야하는데 동일한 거리의 적이 여러명 있으면 가장 왼쪽인 적을 죽인다

=> BFS를 통해 가장 가까운거리를 탐색하고 방향벡터를 [좌 상 우] 방향으로 탐색함으로써 가장 가까운 애들 중 가장 왼쪽에 있는 적을 탐색하게 만든다

why?)

만약 왼쪽에 적이 없었고 상, 우 자리에만 적이 있다면 상에 있는 적이 가장 왼쪽에 있는 적이 될 테니까

방향벡터를 [좌 상 우] 로 해줘야한다.

3. next_round()를 해서 행렬을 아래로 밀어주면 0행은 0으로 초기화가 된다.

4. 적이 궁수자리에 와도 게임이 끝나는게 아니라 제외된다.

5. 게임 라운드는 1행씩 아래로 밀리니까 총 n번 라운드만 진행된다

package practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_17135 {
	static int[][] board;
	static int ans, n, m, d, enemy;
	static int[] archer = new int[3];
	static int[] dx = { 0, -1, 0 };
	static int[] dy = { -1, 0, 1 };

	public static void main(String[] args) throws IOException {
		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());

		board = new int[n + 1][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				int temp = Integer.parseInt(st.nextToken());
				if (temp == 1)
					enemy++;
				board[i][j] = temp;
			}
		}

		combi(0, 0);

		System.out.println(ans);

	}

	public static void combi(int depth, int start) {
		if (depth == 3) {
			int[][] board_temp = new int[n + 1][m]; // 깊은복사
			for (int i = 0; i < n + 1; i++) {
				for (int j = 0; j < m; j++) {
					board_temp[i][j] = board[i][j];
				}
			}

			game(board_temp);

			return;
		}

		for (int i = start; i < m; i++) {
			archer[depth] = i;
			combi(depth + 1, i + 1);
		}
	}

	public static int distance(int x, int y, int x1, int y1) {
		return Math.abs(x - x1) + Math.abs(y - y1);
	}

	public static void next_round(int[][] board) {
		for (int i = n; i > 0; i--) {
			for (int j = 0; j < m; j++) {
				board[i][j] = board[i - 1][j];
			}
		}
		for (int i = 0; i < m; i++) {
			board[0][i] = 0; 
		}
	}

	public static boolean end_test(int cnt,int[][] board, int enemy_cnt) {
		if (enemy_cnt == enemy)
			return false;
		else if(cnt == n)
			return false;

		return true;
	}

	public static int attack(int[][] board) {
		int enemy_cnt = 0;

		for (int k = 0; k < 3; k++) {
			boolean[][] visited = new boolean[n + 1][m];
			Queue<int[]> queue = new ArrayDeque<>();

			queue.add(new int[] { n, archer[k], 0 });
			visited[n][archer[k]] = true;
			while (!queue.isEmpty()) {
				int[] poll = queue.poll();

				if (poll[2] > d)
					break;

				if (board[poll[0]][poll[1]] >= 1) {
					board[poll[0]][poll[1]] = 2;
					break;
				}

				for (int i = 0; i < 3; i++) {
					int nx = poll[0] + dx[i];
					int ny = poll[1] + dy[i];
					if ((0 <= nx) && (0 <= ny) && (nx < n) && (ny < m) && !visited[nx][ny]) {
						visited[nx][ny] = true;
						queue.add(new int[] { nx, ny, poll[2] + 1 });
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 2) {
					enemy_cnt++;
					board[i][j] = 0;
				}
			}

		}
		return enemy_cnt;
	}

	public static void game(int[][] board) {
		int enemy_cnt = 0;
		int cnt=0;
		while (end_test(cnt++,board, enemy_cnt)) {

			enemy_cnt += attack(board);
			next_round(board);

		}
		ans = Math.max(ans, enemy_cnt);
	}

}