[BJ17135] 캐슬 디펜스

 백준 - 캐슬 디펜스 

문제 링크

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

17135번: 캐슬 디펜스

 

문제 입출력

6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

14

6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

9

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {
	static int ans, N, M, D;
	static int[] tgt; // 궁수들의 위치
	static List<Enemy> eOrigin = new ArrayList<>();
	static List<Enemy> e = new ArrayList<>();

	static PriorityQueue<int[]> pq = new PriorityQueue<>(
	    (e1, e2) -> e1[3] == e2[3] ? e1[2] - e2[2] : e1[3] - e2[3]);


	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		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());
		tgt = new int[3];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int m = Integer.parseInt(st.nextToken());
				if (m == 1) eOrigin.add(new Enemy(i, j, false));
			}

		}

		// 조합: 궁수 놓기
		comb(0, 0);

		// 출력
		System.out.println(ans);

	} // end main


	private static void comb(int dep, int idx) {
		if (dep == 3) {
			int max = 0;
			copyEnemy(eOrigin, e);

			do shoot();
			while (down());

			for (int i = 0; i < e.size(); i++) if (e.get(i).isDead) max++;

			ans = Math.max(ans, max);

			return;
		}

		for (int i = idx; i < M; i++) {
			tgt[dep] = i;
			comb(dep + 1, i + 1);
		}

	} // end perm


	private static void shoot() {
		for (int i = 0; i < 3; i++) {
			pq.clear();

			// 사정거리 적 pq에 삽입
			for (int j = 0; j < e.size(); j++) {
				if (!e.get(j).isOut) {
					int dis = extent(e.get(j).y, e.get(j).x, N, tgt[i]);
					if (dis <= D) pq.offer(new int[] { j, e.get(j).y, e.get(j).x, dis });
				}

			}

			// 사정거리 적 중에서 가장 가까운 적 꺼내서 죽이기
			if (!pq.isEmpty()) {
				int[] ne = pq.poll();
				Enemy enemy = e.get(ne[0]);

				enemy.isDead = true;
			}

		}

		for (int i = 0; i < e.size(); i++) {
			if (e.get(i).isDead) e.get(i).isOut = true;
		}

	} // end shoot


	private static boolean down() {
		int out = 0;
		for (int i = 0; i < e.size(); i++) {
			e.get(i).y += 1;

			if (e.get(i).y >= N) e.get(i).isOut = true;
			if (e.get(i).y >= N || e.get(i).isDead) out++;

		}

		if (out == e.size()) return false;

		return true;

	} // end down


	private static void copyEnemy(List<Enemy> src, List<Enemy> tgt) {
		tgt.clear();
		for (Enemy enemy : src) tgt.add(new Enemy(enemy.y, enemy.x, enemy.isDead));
	} // end copyEnemy


	private static int extent(int y1, int x1, int y2, int x2) {
		return Math.abs(y1 - y2) + Math.abs(x1 - x2);
	} // end extent


	static class Enemy {
		int y, x;
		boolean isDead; // 죽었는지 아닌지
		boolean isOut; // 나갔는지 아닌지


		public Enemy(int y, int x, boolean isDead) {
			this.y = y;
			this.x = x;
			this.isDead = isDead;
		}


		@Override
		public String toString() {
			return "Enemy [y=" + y + ", x=" + x + ", isDead=" + isDead + ", isOut=" + isOut + "]";
		}

	} // end Enemy
}

• 푸는 데 서네시간이나 걸렸습니다. 골드 3 맞나요? 흑흑
• 여튼간 전체적인 로직은 다음과 같습니다.
  • 조합으로 궁수의 위치를 구한다.
  • while() 문을 돌며 적을 쏘며, 아래로 한 칸 내린다.
• 궁수의 위치를 두는 것은 문제에도 적혀있다시피, N+1 행 위치에 궁수가 있습니다.
  • 따라서 x 위치만 지정을 하면 되므로 조합에 해당합니다.
• 여기서 중요한 것은 사정거리에 진입한 적 중에서 가장 가까운 적을 쏜다는 것입니다.
  • 이는 PriorityQueue 를 이용해서 구할 수 있습니다.
  • 우선 사정거리 내에 있는 적을 pq 에 넣고, 꺼내서 죽임 처리를 합니다.
• isDead, isOut 변수를 둬서 죽임처리, 아웃처리를 하였습니다.
• 한 칸을 내리는 것은 각 Enemy 노드마다 y 값만 변경해줬습니다.
• 테스트 케이스 중에서 5번 6번이 문제였는데, 6번은 조합을 (0, 2, 4) 등으로 두면 14가 나옵니다.

 

 

 

 

 

 

 

 

 

# 백준 캐슬 디펜스 java # 백준 캐슬 디펜스 6번 테케

---