[BOJ]17135:캐슬 디펜스

이정도 난이도의 구현문제가 그렇듯 "오? bfs/dfs 써서 구현만 딱하면 될거 같은데?" 하고 덤비면 점점 꼬이는 문제.. 7달전의 나처럼..

게임이 진행되는 것과 같이 차근차근 케이스를 나누고 적절한 알고리즘을 대입하면 쉽게 해결할 수 있다.

 

1. 궁수를 배치한다. -> M개의 자리중 3개를 선택하는 문제이므로 재귀를 사용하여 조합을 구현

private static void combination(int cnt, int st) {
	if (cnt == 3) {
		// 궁수 3명 자리 고르기 완료! 조합 완성!
	} else {
		for (int i = st; i < M; i++) {
			archers[cnt] = i;
			combination(cnt + 1, i + 1);
		}
	}
}

 

2. 완성된 조합에서, 몇명의 적을 공격할 수 있는지 알아보자.

2-1) 각 턴마다 궁수들이 공격하는 적들을 구해 공격한다. -> BFS

2-2) 적들을 한칸씩 전진시킨다.

2-3) 게임 필드에서 적들이 사라질 때까지 반복한다.

 

일단, 각 조합마다 게임의 결과를 알아내야 하므로, 주어진 배열을 복사해서 사용하였다.

private static void combination(int cnt, int st) {
	if (cnt == 3) {
		int[][] gameCase = copyGame(); // 주어진 격자판 복사 
        	int originEnemy = enemy; // 격자판 위 적의 수 
		int kill = 0; // 해당 조합에서 제거할 수 있는 적의 수
        
        	// ...
		enemy = originEnemy;
	} else {
		// ...
	}
}

 

2-1 이 이번 문제에서 가장 까다로웠던 부분이였다. 궁수는 가장 왼쪽의 적부터 공격하며, 같은 적이 여러 궁수에게 공격 당할 수 있다는 조건 때문이다. 따라서 BFS로 탐색할 때, 좌 -> 상 -> 우 순으로 탐색하였으며, 궁수마다 BFS를 돌려 공격할 수 있는 적의 좌표를 알아냈다.

3명의 궁수에 대해 BFS를 각각 진행하여 완료한 후, 적을 공격해야 문제의 조건을 만족 시킬수 있다.

이 부분을 섬세하게 구현했다면, 적을 전진시키는 2-2와 함께 적이 격자판에서 사라질 때까지 반복하면 된다.

private static void combination(int cnt, int st) {
	if (cnt == 3) {
        	// ...
            while (enemy > 0) {
			kill += attack(gameCase); // 해당 턴에 궁수가 공격하여 제거하는 적의 수
			forward(gameCase); // 적 전진
		}
		enemy = originEnemy;
	} else {
		// ...
	}
}

private static int attack(int[][] gameField) {
	// 왼쪽부터 적을 탐색하기 위한 조건
	int[] dx = {0, -1, 0};
	int[] dy = {-1, 0, 1};
    
    	List<int[]> targets = new LinkedList<>(); // 제거할 수 있는 적의 좌표

	for (int archer: archers) {
    	// BFS를 사용하여 각 궁수마다 공격 가능한 적 탐색 
    	Queue<int[]> queue = new LinkedList<>();
		int[][] vis = new int[N + 1][M];
    	
        //...
 	}
    
   	// 적 제거
	int kill = 0;
	for (int[] target : targets) {
		if (gameField[target[0]][target[1]] == 1) {
			gameField[target[0]][target[1]] = 0;
			enemy--;
			kill++;
		}
	}
    
    	// 제거한 적의 수 반환
	return kill;
}

 

 

3. 모든 경우에 대해 2번을 반복해서 제거할 수 있는 적의 최대수를 구한다.

private static void combination(int cnt, int st) {
	if (cnt == 3) {
    		int kill = 0;
        	// ...
        	maxKill = Math.max(kill, maxKill);
	} else {
		// ...
	}
}

 

전체 코드는 깃허브에 올려두었다.

https://github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/Simulation/p17135.java

GitHub - SuyeonChoi/Algorithms: Personal Algorithm Study::solving BOJ, Programmers, and SW Expert Academy

 

엄청나게 어려운 문제는 아니지만 이전에 던져버린 문제를 단번에 해결해서 기분이 좋다:)