[백준BOJ] 17135번 캐슬 디펜스.java

 

백준 저지에서 캐슬 디펜스를 자바를 통해 풀어 보았다. 

 

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

17135번: 캐슬 디펜스

17135번 캐슬 디펜스.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

17135번 캐슬 디펜스

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

설명

아래 코드를 보면 알겠지만 문제 스토리가 엄청 길다. 문제 난이도 자체는 조합을 통한 완전탐색으로 어렵지 않은 편인데 문제의 호흡이 너무 길어 풀다가 자칫 이상한데서 실수라도 하면 실수한 코드를 찾는데 시간이 오래 걸릴 것이다.

 

격자판에는 적이 존재하고 격자판 바로 아래에는 성이 있다. 문제에서는 격자판만 주어지지만 그 아래 하나의 행이 더 있다고 생각해야한다. 아래의 행에는 3명의 궁수가 위치한다. 

 

격자판에 있는 적은 턴마다 한칸 씩 내려오며 궁수의 사거리에 들어오면 궁수한테 맞아 죽게된다. 궁수의 배치에 따라 죽일 수 있는 적의 수는 달라질 것이며 가장 많은 적을 죽이는 궁수의 위치를 찾는 것이 목표다. 

 

단 궁수는 한 턴에 같은 적을 노릴 수도 있다. 즉 궁수는 3명이지만 경우에 한 턴에 죽일 수 있는 최대의 적의 수가 3명일 뿐 무조건적으로 3명을 죽이는 것은 아니다.

 

A. 먼저 궁수의 위치를 골라야한다. 궁수는 격자판 아래에 있는 가상의 행에 위치하며 M개의 격자 중 3곳에 위치할 수 있다. 여기서 조합을 통해 궁수의 위치를 선택한다.

 

1. 궁수를 선택했으면 디펜스를 시작한다. 각 궁수는 어떤 적을 죽일지 선택한다. 단 선택하자마자 바로 죽이면 안 된다. 다른 궁수도 해당 적을 선택할수도 있기 때문이다. 각 궁수는 모든 적에 대해서 가장 가까우면서 최대한 왼쪽에 있는 적을 선택한다.

 

2. 세 궁수가 모두 죽일 적을 선택했으면 선택한 적을 죽이는 과정을 거친다. 궁수가 사거리가 닿지 않아 적을 선택 못 하거나 궁수끼리 중복되게 적을 선택한다면 3명 미만의 적을 죽이는 경우도 있을 것이다.

 

3. 적을 죽이는 과정을 완료 했으면 적들은 모두 한 칸씩 내려온다. 만약 이동한 격자판이 격자판을 벗어난다면 적은 격자판에서 제외된다.

 

B. 1~3의 과정을 격자판에 적이 아무도 없을 때까지 반복한다. 반복을 완료하면 A에서 구한 궁수의 위치에서의 죽인 적의 수를 구할 수 있다.

 

가능한 모든 궁수의 위치에 대해서 A~B의 과정을 통해 각 조합에서 죽일 수 있는 적의 수를 구하고 그 중 최댓값을 구한다.

코드

//17135번 캐슬 디펜스.java
package com.ssafy.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 캐슬_디펜스_17135 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb; 
    
    static int N;
    static int M;
    static int D;
    
    static List<enemy> e = new ArrayList<enemy>();
    static List<archer> a = new ArrayList<archer>();
    static int p[];
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		List<enemy> eCopy = new ArrayList<enemy>();
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<M;j++) {
				if(st.nextToken().equals("1")) {
					e.add(new enemy(i, j));
					eCopy.add(new enemy(i, j));
				}
			}
		}
		
		p = new int[M];
		for(int i=M-1;i>=M-3;i--) {
			p[i]=1; //조합
		}
		
		do {//각각 궁수의 자리 -> 제거할 수 있는 적의 수를 구해야함
			int nowDieEnemyCount=0;
			a = new ArrayList<archer>();//궁수 위치 초기화
			e = new ArrayList<enemy>();//적 위치 초기화
			//e에 eCopy를 깊은 복사
			for(int i=0;i<eCopy.size();i++) e.add(new enemy(eCopy.get(i).i, eCopy.get(i).j));
			
			for(int i=0;i<M;i++) {
				if(p[i]==1) {//궁수의 위치 (N,i)
					a.add(new archer(N, i));
				}
			}//궁수 리스트에 궁수들 넣어줌
			
			//격자판에 적이 아무도 없을 때까지 수행
			while(!e.isEmpty()) {
				//제거할 수 있는 적의 수 구하기
				List<enemy> nowDie = new ArrayList<enemy>();
				for(int archerNum = 0;archerNum<3;archerNum++) {
					//죽일 수 있는 적 선택
					int minDis=Integer.MAX_VALUE;
					int eNum=-1;//죽이는 적의 번호
					int eLeft=M;//죽이는 적의 j좌표
					for(int enemyNum = 0;enemyNum<e.size();enemyNum++) {
						int dis = Math.abs(a.get(archerNum).i-e.get(enemyNum).i)+Math.abs(a.get(archerNum).j-e.get(enemyNum).j);
						if(dis<=D) {
							if(dis<minDis) {
								minDis = dis;
								eNum=enemyNum;
								eLeft = e.get(enemyNum).j;
							}
							else if(dis == minDis) {
								if(e.get(enemyNum).j < eLeft) {
									minDis = dis;
									eNum=enemyNum;
									eLeft = e.get(enemyNum).j;
								}
							}
						}
					}
					//죽이겔 될 적 선택 완료
					if(eNum!=-1) {
						nowDie.add(e.get(eNum));
					}
				}
				//적 죽이기
				for(int i=0;i<nowDie.size();i++) {
					for(int j=0;j<e.size();j++) {
						if(nowDie.get(i).i==e.get(j).i && nowDie.get(i).j==e.get(j).j) {
							e.remove(j);
							nowDieEnemyCount++;
						}
					}
				}
				//궁수 공격 완료 후 적들 한칸씩 아래로
				for(int i=0;i<e.size();i++) {
					if(e.get(i).i+1==N) {
						e.remove(i);
						i--;
					}
					else {
						e.get(i).i += 1;
					}
				}
			}
			answer = Math.max(answer, nowDieEnemyCount);
		}while(np(p));
		
		System.out.println(answer);
	}
	private static boolean np(int[] numbers) {
		int N = numbers.length;
		int i=N-1;
		while(i>0 && numbers[i-1]>=numbers[i])--i;
		
		if(i==0)return false;
		
		int j=N-1;
		while(numbers[i-1]>=numbers[j])--j;
		
		swap(numbers, i-1,j);
		
		int k=N-1;
		while(i<k) {
			swap(numbers,i++,k--);
		}
		
		return true;
	}
	
	private static void swap(int[] numbers, int i, int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
	
}

class enemy{
	int i;
	int j;
	enemy(int i, int j){
		this.i = i;
		this.j = j;
	}
}
class archer{
	int i;
	int j;
	archer(int i, int j){
		this.i = i;
		this.j = j;
	}
}