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

➊ 문제 이해

N X M 행렬에 몬스터의 위치가 랜덤으로 주어진다.
이때 행렬의 가장 아래 부분에 궁수가 3명 위치한다.

궁수는 M개의 자리 중에서 3자리를 선택해야 한다.

시뮬레이션이 시작되면 3명의 궁수는 동시에 적을 공격한다.
이때 같은 적을 공격할 수 있으며 🚨
궁수가 공격할 적을 고르는 기준은 다음과 같다.

ⓐ 궁수가 공격하는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이다.
ⓑ 거리가 같다면, 가장 왼쪽에 있는 적을 공격한다.

궁수가 몬스터를 공격하면 몬스터는 게임판에서 제거된다.

제거되지 않은 나머지 몬스터들은 아래로 한 칸씩 전진한다.
또한 가장 아래쪽에 위치한 몬스터가 전진하면 게임판에서 제거된다.

시뮬레이션의 종료 조건은 다음과 같다.

게임판 위에 몬스터의 수가 0이어야 한다.

그리고 우리의 목적은,
가장 많은 몬스터를 공격할 수 있는 궁수의 위치(조합)를 찾고
그 몬스터의 수를 출력 🌟 하는 것이다.

➋ 문제 풀이

문제를 해결하는 전체 과정은 다음과 같다.

① 궁수가 위치할 수 있는 모든 조합을 구하고,
② 각 조합에 대하여 시뮬레이션을 진행하였다.
③ 시뮬레이션이 종료되면 최대로 kill한 몬스터 수를 갱신하였다.

이러한 과정을 수행하기 위해 기능별로 5개의 메소드로 분리하였다.

• init : 입력을 위함
• makeCombination : 궁수가 위치할 수 있는 조합을 구함
• gameStart : 전체적인 시뮬레이션 로직을 수행
• kill : 궁수가 몬스터를 향해 공격
• moveMonster : 몬스터가 성을 향해 아래로 전진

각 메소드에 대해 차례로 설명하도록 하겠다.

① init

게임판의 가로, 세로 길이, 궁수의 공격 범위, 몬스터의 배치 정보를 입력받는다!

② makeCombination

3명의 궁수를 배치할 수 있는 조합은 3중 for문으로 구현하였다.
뽑을 개수가 3개로 정해져 있기 때문에 재귀보다 for문으로 조합을 구하는 것이 더 효율적이라 판단하였다.

왜냐하면,
재귀로 구현하게 되면 함수 호출이 중첩되기 때문에 스택 프레임을 계속해서 할당하고 해제하는 작업이 반복되기 때문에 for문보다 성능이 저하되기 때문이다.

위의 코드에서 궁수의 index(column) 을 결정하고 choosed 배열에 저장해주었다!

③ gameStart

본격적으로 시뮬레이션을 실행하는 메소드이다.

무한 루프를 돌면서 시뮬레이션을 반복 실행한다.
모든 적이 격자판에 없으면 최대 kill 수를 갱신하며 무한 루프를 탈출한다.

④ kill 👾

맨해튼 거리를 이용하여 궁수의 공격 범위 안에 있는지 계산하였다.
궁수가 어떤 적을 공격할 건지 고르는 기준은 생각보다 까다롭다!
문제를 다시 읽어보자.

궁수가 공격하는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고,
그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
같은 적이 여러 궁수에게 공격당할 수 있다.

따라서 공격 범위가 1, 2, 3, ..., D일 때까지의 경우를 순차적으로 따져보았다.
또한 가장 왼쪽에 있는 적부터 공격해야 하기 때문에
왼쪽 열부터 순회하여 공격할 수 있는 적을 탐색했다.

해당 좌표에 몬스터가 존재하고 맨해튼 거리도 만족한다면
killed 배열에 몬스터 좌표를 저장하였다.

바로 게임맵에서 몬스터를 제거하지 않은 이유는,
다른 궁수가 동시에 같은 몬스터를 공격할 수 있기 때문이다!

⑤ moveMonster

궁수의 공격이 끝났다면 몬스터가 아래로 한 칸씩 이동할 차례다.

가장 아래 행에 있는 몬스터는 게임맵에서 제거해야 한다.
따라서 현재 몬스터 수를 뜻하는 curMonsterCount을 1 감소시켜주었다!

➌ 전체 코드

package algorithm;

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

public class 캐슬디펜스 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer tokens;

	private static int N;
	private static int M;
	private static int D; // 공격 거리 제한

	private static int[][] map; // 적의 배치 정보
	private static int[][] curMap; // 현재 적의 배치 정보
	private static int[] choosed; // 선택한 궁수의 column 인덱스
	private static int[][] killed; // 궁수가 공격한 적의 row, column 좌표

	private static int monterCount; // 총 살아있는 적 개수
	private static int curMonterCount; // 현재 살아있는 적 개수
	private static int maxKillCount; // 출력하고자 하는 답

	// 적 이동
	private static void moveMonster() {
		// 가장 아래에 있는 적 제외
		for (int j = 0; j < M; j++) {
			if (curMap[N - 1][j] == 1) {
				curMonterCount--;
			}
		}

		// 적 위치 아래로 한 칸씩 이동
		for (int i = N - 2; i >= 0; i--) {
			for (int j = 0; j < M; j++) {
				curMap[i + 1][j] = curMap[i][j];
			}
		}

		// 맨 위의 행은 비워야 함
		for (int j = 0; j < M; j++) {
			curMap[0][j] = 0;
		}
	}

	// 궁수가 적을 공격
	private static void kill(int index, int archerColumn) {
		for (int k = 1; k <= D; k++) {
			for (int j = 0; j < M; j++) {
				for (int i = N - 1; i >= 0; i--) {
					if (curMap[i][j] == 1 && Math.abs(N - i) + Math.abs(archerColumn - j) == k) {
						killed[index] = new int[] { i, j };
						return;
					}
				}
			}
		}

		// 공격할 수 없으면 0 저장
		killed[index] = new int[] { N, 0 };
	}

	// 게임 시작
	private static void gameStart() {
		int killCount = 0;
		curMonterCount = monterCount;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				curMap[i][j] = map[i][j];
			}
		}

		while (true) {
			// 모든 적이 격자판에 없으면 게임 종료
			if (curMonterCount == 0) {
				maxKillCount = Math.max(maxKillCount, killCount);
				return;
			}

			// 모든 궁수 공격
			for (int i = 0; i < 3; i++) {
				kill(i, choosed[i]);
			}

			// 제거한 적의 수 카운트
			for (int[] coord : killed) {
				int r = coord[0];
				int c = coord[1];
				if (curMap[r][c] == 1) {
					curMap[r][c] = 0;
					curMonterCount--;
					killCount++;
				}
			}

			// 적 앞으로 전진
			moveMonster();
		}
	}

	// 궁수의 위치 3개를 선택하는 조합 생성 
	// 각 조합에 대하여 시뮬레이션 실행
	private static void makeCombination() {
		for (int i = 0; i < M; i++) {
			for (int j = i + 1; j < M; j++) {
				for (int k = j + 1; k < M; k++) {
					choosed[0] = i;
					choosed[1] = j;
					choosed[2] = k;
					// 게임 시작
					gameStart();
				}
			}
		}
	}

	// 입력
	private static void init() throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		D = Integer.parseInt(tokens.nextToken());

		map = new int[N + 1][M];
		curMap = new int[N + 1][M];
		choosed = new int[3];
		killed = new int[3][2];
		monterCount = 0;
		curMonterCount = 0;
		maxKillCount = 0;

		for (int i = 0; i < N; i++) {
			tokens = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(tokens.nextToken());
				if (map[i][j] == 1) {
					monterCount++;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		init();
		makeCombination();
		System.out.println(maxKillCount);
	}

}