[BOJ/Java] 17135 : 캐슬 디펜스

문제

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

풀이

바로 이전에 풀었던 아기상어 문제와 상당히 비슷했다

    - 처음 설계

고려해야 하는 부분

• 궁수들은 같은 적을 공격할 수 있다 / 모든 궁수는 동시에 공격한다 - 첫 번째 궁수가 공격할 적을 바로 삭제해버리면 두 번째 궁수가 공격할 적이 바뀔 수도 있다. 따라서 각 궁수가 공격할 적을 모두 정한 다음에 한 번에 공격해야 한다

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {// 캐슬 디펜스
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { 0, 1 },  { -1, 0 }, { 0, -1 }, { 1, 0 } };
	static int[][] map;
	static int[][] original;
	static int n, m, d;
	static boolean[] isSelected;
	static int[] attacker = new int[3];
	static boolean[][] visited;
	static Queue<Node> queue = new LinkedList<>();
	static Queue<enemy> enemiesA = new LinkedList<>();//거리 d이하인 적들을 넣어줄 큐
	static Queue<enemy> enemiesB = new LinkedList<>();
	static Queue<enemy> enemiesC = new LinkedList<>();
	static int count, maxCount;

	public static void combination(int cnt, int start) {
		if (cnt == 3) {
			attack(attacker[0], attacker[1], attacker[2]);
			// System.out.println(Arrays.toString(attacker));
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= m; j++) {
					map[i][j] = original[i][j];
				}
			}
			
			return;
		}
		for (int i = start; i <= m; i++) {
			attacker[cnt] = i;
			combination(cnt + 1, i + 1);
		}
	}

	public static void attack(int A, int B, int C) {
		// 궁수 위치 설정
		int[] attackerLocation = { A, B, C };
		count = 0;
		while (true) {
			for (int l : attackerLocation) {
				visited = new boolean[n + 2][m + 1];
				queue.offer(new Node(n + 1, l, 0));
				while (!queue.isEmpty()) {
					Node temp = queue.poll();
					int x = temp.x;
					int y = temp.y;
					int dist = temp.dist;
					if (dist >= d)
						continue;
					visited[x][y] = true;
					for (int d = 0; d < 4; d++) {
						int dx = x + dir[d][0];
						int dy = y + dir[d][1];

						if (dx <= 0 || dy <= 0 || dx > n || dy > m)
							continue;
						if (visited[dx][dy])
							continue;
						if (map[dx][dy] == 1) {
							visited[dx][dy] = true;
							if (l == A) {
								enemiesA.offer(new enemy(dx, dy, dist + 1, 0, 0));
							} else if (l == B) {
								enemiesB.offer(new enemy(dx, dy, 0, dist + 1, 0));
							} else if (l == C) {
								enemiesC.offer(new enemy(dx, dy, 0, 0, dist + 1));
							}
							queue.offer(new Node(dx, dy, dist + 1));
						} else {
							visited[dx][dy] = true;
							queue.offer(new Node(dx, dy, dist + 1));
						}
					}
					dist++;
				}

			}
			// 공격할 적 선정하기
			enemy targetA = null, targetB = null, targetC = null;
			if (!enemiesA.isEmpty()) {
				targetA = enemiesA.poll();
				for (enemy e : enemiesA) {//거리가 가장 가까우면서도 왼쪽에 있는 적을 target으로 선정
					if (e.distA <= targetA.distA && e.y < targetA.y) {
						targetA = e;
					}
				}
			}
			if (!enemiesB.isEmpty()) {
				targetB = enemiesB.poll();
				for (enemy e : enemiesB) {
					if (e.distB <= targetB.distB && e.y < targetB.y) {
						targetB = e;
					}
				}
			}
			if (!enemiesC.isEmpty()) {
				targetC = enemiesC.poll();
				for (enemy e : enemiesC) {
					if (e.distC <= targetC.distC && e.y < targetC.y) {
						targetC = e;
					}
				}
			}

			// 공격 후 없애주고 count+1 해주기, 만약 다른 궁수가 이미 공격해서 0이 되었다면 count하지 않는다
			if (targetA != null && map[targetA.x][targetA.y] == 1) {
				map[targetA.x][targetA.y] = 0;
				count++;
			}
			if (targetB != null &&map[targetB.x][targetB.y] == 1) {
				map[targetB.x][targetB.y] = 0;
				count++;
			}
			if (targetC != null && map[targetC.x][targetC.y] == 1) {
				map[targetC.x][targetC.y] = 0;
				count++;
			}

			move();//적이 한 칸씩 내려온다
			
			if (!isEnemy())//적이 모두 사라지면 while문을 빠져나옴
				break;
			
			//적의 정보를 넣은 큐를 clear해주고 적이 움직인 위치에서 다시 while문이 돌아간다
			enemiesA.clear();
			enemiesB.clear();
			enemiesC.clear();
		}

		if (maxCount < count)
			maxCount = count;
		//System.out.println(count);
	}

	public static void move() {//적이 한 칸씩 내려온다
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= m; j++) {
				if (map[i][j] == 1) {
					if (i < n) {
						map[i + 1][j] = 1;
						map[i][j] = 0;
					} else if (i == n) {//성이 있는 칸으로 이동한 경우 제외한다
						map[i][j] = 0;
					}
				}
			}
		}
	}

	public static boolean isEnemy() {
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= m; j++) {
				if (map[i][j] == 1)
					return true;
			}
		}
		return false;
	}

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

		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		isSelected = new boolean[m + 1];
		map = new int[n + 2][m + 1]; // n+1행에는 궁수가 있다

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 1; j <= m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		original= new int[n+2][m+1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				original[i][j] = map[i][j];
			}
		}

		combination(0, 1);
		System.out.println(maxCount);


	}

	static class Node {
		int x, y, dist;

		Node(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}

	static class enemy {
		int x, y, distA, distB, distC; // 위치와 궁수로부터 떨어진 거리

		enemy(int x, int y, int distA, int distB, int distC) {
			this.x = x;
			this.y = y;
			this.distA = distA;
			this.distB = distB;
			this.distC = distC;
		}

	}

}

 

느낀점

• 테케는 맞는데 자꾸 틀렸습니다 나왔던 이유가 다 오타때문이었다 ... 조심하자
• 중복을 최소화하자