[BOJ] 백준 17135 - 캐슬 디펜스 풀이

1. 문제

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

17135번: 캐슬 디펜스

2. Error Point

• (1) 같은 적이 여러 궁수에게 공격당할 수 있다.
  • 문제에서는 궁수의 공격으로 제거할 수 있는 적의 최대 수를 요구한다.
  • 처음 드는 생각은 최대 수가 나오려면 최대한 겹치지 않게 공격을 해야한다고 생각했다.
  • 그러면 중복으로 적을 고르는 경우는 어떻게 처리해줘야하지???
  • → 궁수 별로 적을 처치한 수를 카운트 하는 것이 아니기에 내 이전 궁수가 적을 골랐다면 나는 그 적을 고르지 않고 가능한 다른 적을 고르면 되는 것이다
• (2) 모든 궁수는 동시에 공격한다.
  • 동시에 공격하는 것은 어떻게 구현해야 할까??
  • → 궁수 별로 적을 고른 후, 모든 궁수가 적을 골랐다면 한꺼번에 적을 처리한다.
    
    
    

3. 풀이 Point

• static Class인 Enemy를 선언한다. (x == 행 값, y == 열 값, dist == 궁수로부터 해당 적까지의 거리)
• 격자판의 값을 입력 받을 때 적의 위치를 미리 enemyList에 저장한다.
• setArcher()를 통해 궁수 3명을 선택한다. 이때 true가 된 위치가 궁수의 위치.
• 그 후 gameStart()를 통해 게임을 시작한다.
  1. 우선 백트래킹으로 궁수의 위치를 선택해주었으므로 copyEnemyList를 통해 적의 위치를 복사한다.
  2. selectedEnemyList를 선언하여 궁수가 선택한 적을 담을 리스트를 만든다.
  3. 궁수 한 명당 다음을 반복한다.
     1. 우선순위 큐를 통해 적을 추가한다. (거리가 가까운 순으로, 그 것이 여러개라면 왼쪽) 이때 사거리인 D를 넘어가서는 안된다.
     2. 우선 순위 큐가 빌 때까지 반복문을 돌아준다.
        1. 큐에서 꺼낸 적이 어떤 궁수도 선택하지 않은 적이라면 selectedEnemyList에 넣는다.
        2. 큐에서 꺼낸 적이 다른 궁수가 선택한 적이라면 flag를 true로 만들어 다음으로 넘긴다.
  4. 처음 적을 담았던 리스트(여기선 copy한 리스트를 말한다.)와 선택한 적을 담은 리스트를 비교하여, 두 리스트에 같은 값을 처음 적을 담았던 리스트에서 지우고 카운트를 하나씩 올린다. (적을 처치했음)
  5. selectedEnemyList에 남아있는 적은 한 칸 밑으로 내려와야 하므로 객체의 x 값에 +1을 해준다. 이때 그 값이 궁수의 위치와 같다면 그 적은 제외시킨다.
  6. 마지막으로 result를 갱신해주면 정답.
     
     
     

4. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, D; 			// N : 행 수, M : 열 수, D : 궁수의 사거리
	static int[][] map;				// 격자판
	static boolean[] archerVisited; // 궁수를 선택할 visited 배열
	static int result = 0;			// 결과 값
	
	static class Enemy {
		int x;    
		int y;
		int dist; // 궁수로부터 적까지의 거리
		
		public Enemy(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
	
	static PriorityQueue<Enemy> pq;  // 게임 중 적 우선순위를 판단할 큐 
	static List<Enemy> enemyList = new ArrayList<>(); // 처음 적의 위치를 저장할 배열
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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());
        		
        		if (map[i][j] == 1) {
        			enemyList.add(new Enemy(i, j, 0));
        		}
        	}
        }
        
        archerVisited = new boolean[M];
        setArcher(3, 0);
        
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 궁수 셋팅
    private static void setArcher(int ahCnt, int depth) {
    	if (ahCnt == 0) {
    		gameStart();
    		return;
    	}
    	
    	for (int i = depth; i < M; i++) {
    		if (archerVisited[i]) continue;
    		
    		archerVisited[i] = true;
    		setArcher(ahCnt - 1, i + 1);
    		archerVisited[i] = false;
    	}
    }

    // 게임 시작
	private static void gameStart() {
		int killCnt = 0;		// 처치한 적 수
		
		// 최대 마리수를 구해야 하므로 적을 제거한채로 끝내면 안된다.
		// 따라서 처음 적을 저장한 리스트를 복제할 필요성이 있음.
		List<Enemy> copyEnemyList = new ArrayList<>();
		for (int i = 0; i < enemyList.size(); i++) {
			int x = enemyList.get(i).x;
			int y = enemyList.get(i).y;
			
			copyEnemyList.add(new Enemy(x, y, 0));
		}
		
		while (true) {
			// 남아 있는 적이 없다면 탈출
			if (copyEnemyList.isEmpty()) break;
			
			// 궁수들이 동시에 공격할 수 있으므로 궁수가 선택했는지 저장하는 리스트
			List<Enemy> selectedEnemyList = new ArrayList<>();
			
			for (int i = 0; i < M; i++) {
				if (archerVisited[i]) {
					
					// 우선 순위 체크
					pq = new PriorityQueue<>(new Comparator<Enemy>() {
						@Override
						public int compare(Enemy o1, Enemy o2) {
							if (o1.dist == o2.dist) {
								return o1.y - o2.y;
							}
							return o1.dist - o2.dist;
						}
					});
					
					// 우선순위에 따른 적 위치 추가
					for (int j = 0; j < copyEnemyList.size(); j++) {
						Enemy t = copyEnemyList.get(j);
						int t_dist = Math.abs(N - t.x) + Math.abs(i - t.y);
						if (t_dist <= D) {
							pq.add(new Enemy(t.x, t.y, t_dist));
						}
					}
					
					// 남아있는 적이 있다는 얘기
					if (!pq.isEmpty()) {
						boolean flag = false;
						Enemy poll = pq.poll();
						for (int j = 0; j < selectedEnemyList.size(); j++) {
							Enemy f = selectedEnemyList.get(j);
							if (poll.x == f.x && poll.y == f.y) {
								flag = true;
							}
						}
						
						if (!flag) selectedEnemyList.add(new Enemy(poll.x, poll.y, 0));
					}
				}
			}
			
			// 선택한 적과 처음에 적을 저장한 list와 비교하면서 처치하기
			for (int j = 0; j < selectedEnemyList.size(); j++) {
				Enemy s = selectedEnemyList.get(j);
				
				for (int k = copyEnemyList.size() - 1; k >= 0; k--) {
					Enemy f = copyEnemyList.get(k);
					
					if (f.x == s.x && f.y == s.y) {
						copyEnemyList.remove(k);
						killCnt++;
					}
				}
			}
			
			// 적 움직이기.
			for (int j = copyEnemyList.size() - 1; j >= 0; j--) {
				copyEnemyList.get(j).x += 1;
				
				// 적의 위치가 궁수의 위치일 경우 : 적 제외
				if (copyEnemyList.get(j).x == N) copyEnemyList.remove(j);
			}
		}
		
		result = Math.max(result, killCnt);
	}
}

5. 배운점

• List.get(”index”)는 값 복사가 아닌 주소값 연결이다.
• 동시에 처리해야할 일은 개체 들이 할 일을 선택한 후 비교하면서 처리하는 방법도 있다.(꼭 BFS Queue에 미리 넣어둘 필요는 없다.)
  
  
  

6. 점수

50/100