Baekjoon 17135 캐슬 디펜스 JAVA

17135번: 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1 ×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N 번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져 있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

 

조건

[입력]

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈칸, 1은 적이 있는 칸이다.

 

[출력]

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

 

풀이

해당 문제는 예전에 싸피에서 수업을 들었던 적 있는 문제로 당시는 해결을 하지 못했지만 이번에 풀어보자는 생각으로 문제를 해결할 수 있었다. 문제는 map에 적의 정보가 주어졌을 때 궁수 3명이서 최대한 적을 많이 죽이는 최댓값을 구하는 문제다.

전형적인 시뮬레이션 문제로 예전 풀이 코드를 참고하여 문제를 해결했으며 최초 문제를 해결하기 위해 생각한 방법과는 다른 방법으로 해결하였다.

 

처음에는 궁수 별로 bfs를 돌면서 가장 가까운 적의 좌표를 기억하는 방식으로 적을 제거하면서 해결하면 되겠다고 생각했고 풀이 코드에서는 심플하게 우선순위 큐를 이용해서 해결한 것을 보고 신박해서 해당 풀이 코드를 참고하여 해결했다.

다음에 시간이 되면 내 생각대로 한번 다시 풀어봐야겠다 로직은 아래와 같다.

 

1. 입력 처리를 한다.

2. 조합을 이용해 궁수의 위치 경우의 수를 구한다 (1,2,3 ~ M-2, M-1, M)

3. 조합이 완성될 때마다 체크한다.

    1. 리스트에 적의 좌표값을 경신한다.

    2. 시뮬레이션을 돌린다.

        1. 궁수의 수만큼 반복을 돌리면서 궁수 별로 죽일 수 있는 적을 우선순위 큐에 담는다.

        2. 큐가 비지 않았다면 가장 첫 번째 적을 사망 처리한다.

        3. 리스트를 탐색하면서 사망된 적 제거, 범위 밖으로 나갈 적 제거하고 적들 이동시킨다.

        4. 만약 리스트가 비었다면 종료한다.

        5. 최댓값을 경신한다.

4. 시뮬레이션이 종료되면 결괏값을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, D, ans, map[][], out[] = new int[3];
	static List<Node> list = new LinkedList<>();
	static PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.d == b.d ? a.x - b.x : a.d - b.d);
	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());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		comb(0,0); // 조합 (1,2,3 ~ M-2, M-2, M)
		System.out.println(ans);
	}
	
	private static void comb(int index, int target) { // 조합으로 3 궁수의 위치를 만듬.
		if(target == 3) {
			check(); // 조합이 완성되면 체크하기 
			return;
		}
		if(index == M)
			return;
		
		out[target] = index;
		comb(index+1, target+1);
		comb(index+1, target);
	}

	private static void check() {
		list.clear(); // 적이 담긴리스트 초기화 (이전값들 삭제)
		for (int i = 0; i < N; i++) { // 적 위치 경신 
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 1)
					list.add(new Node(i,j));
			}
		}
		int cnt = 0;
		while(true) {
			for (int i = 0; i < 3; i++) {
				pq.clear(); // 궁수마다 적의 거리가 다르기때문에 초기화 실시 
				
				for (int j = 0; j < list.size(); j++) {
					Node n = list.get(j);
					n.d = Math.abs(n.x - out[i]) + Math.abs(n.y - N); // 적 위치 즉 거리를 경신한다.
				
					if(n.d <= D) // 죽일수 있으면 우선순위 큐에 담음 
						pq.add(n);
				}
				if(!pq.isEmpty()) // 가장 첫번째 적만 죽임 우선순위 큐에의해 자동 정렬 
					pq.poll().life = true;
			}
			for (int i = 0; i < list.size(); i++) { // 여기는 적 이동 및 사망된적 삭제 
				Node n = list.get(i);
				if(n.life) { // 적이 죽은 경우 
					list.remove(n);
					cnt++;
					i--; // 위에서 리스트를 하나 제거했기때문에 사이즈가 1 줄어듬 
				}else if(n.y == N-1) {// 이제 성밖으로 이동한경우 
					list.remove(n);
					i--;
				}else // 적 한칸씩 이동 
					n.y++;
			}
			if(list.size() == 0) // 적이 모두 죽거나 성밖으로 나가면 종료 
				break;
		}
		ans = Math.max(ans, cnt);
	}

	static class Node{
		int y,x,d;
		boolean life;
		Node(int y,int x){
			this.y = y;
			this.x = x;
		}
	}

}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드