[백준/구현] 17135: 캐슬디펜스 - 자바

문제

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

17135번: 캐슬 디펜스

 

풀이

조합으로 궁수의 위치를 뽑고 시뮬레이션을 하였다.

다른 풀이를 보면 BFS를 사용해 궁수부터 적 위치까지 탐색을 한 풀이들이 많은데 

 

본인은 그렇게 하지않고 왼쪽 하단 부터 오른쪽 상단까지 열 순서가 아닌 행 순서로 탐색하였다.(좌 하->상 ... 우 하->상)

그리고 탐색하면서 시간마다 적이 성벽에 닿으면 사라진다.

배열을 N+1, M 크기만큼 구현하여 N+1 위치에 성벽 위치를 지정하였다. 

그리고 시간이 한턴씩 흐를 수록 적이 성벽에 오면 죽는 것을 성벽을 한칸씩 올려서 구현하였다.

 

아래 그림을 통해 이해에 도움이 되었으면 한다. 

 

아래 그림은 예제 5번을 나타내었다.

주황색은 적을 나타내며 회색은 성벽을 나타내었다. 

회색 성벽에 위치한 궁수마다 적을 탐색하였다.

적은 행 먼저 탐색을 하고(보라색) 행 탐색이 완료되면 열 순서(파란색)로 탐색하였다

(성벽의 파란색 부분이 궁수가 위치한 곳, 빨간색이 궁수가 죽인 적 위치를 나타내었다.)

먼저 턴이 한번 진행되면 다음과 같이 적을 죽인다. (아직 1턴에서는 거리가 1이므로 적을 죽일 수 없다)

이후에 한칸씩 성벽을 위로 올린다.

(성벽의 파란색 부분이 궁수가 위치한 곳, 빨간색이 궁수가 죽인 적 위치를 나타내었다.)

턴2

턴3

이런식으로 성벽을 n이 1일때까지 반복하면서 적을 죽인 횟수를 구하였다.

 

문제에서 궁수가 범위내에 동일한 적을 죽일 수 있는데 가장 왼쪽의 적을 죽이므로 적을 죽인 횟수를 중복하여 세지 않도록 하는 것이 중요하다. 

다음과 같은 상황에서 2번째 궁수는 파란색 원의 적을 3번째 궁수는 파란색 보라색 원을 죽일 수 있다.

문제에서 같은 거리 내의 적은 왼쪽을 우선순위로 먼저 죽이므로 2번째 궁수와 3번째 궁수는 파란색 원의 적을 처치할 수 있고 죽인 횟수는 중복해서 구하지 않음을 유의한다. 

 

아래는 위의 과정을 구현한 코드이다. 

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

public class BOJ_17135 {
	static final int ARCHER_NUMBER = 3;
	static int killEnemyNumber = Integer.MIN_VALUE;
	static int N, M, D;
	static int[] archer = new int[ARCHER_NUMBER];
	static int[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		inputData();
		comb(0, 0);
		bw.write(String.valueOf(killEnemyNumber));
		bw.flush(); bw.close();
	}
	
	public static void solution() {
		int[][] copyMap = copyMap(); // 아처가 성벽에 있는 경우의 수 마다 최대값 계산하므로 원래의 맵 복사
		int caseResult = 0;
		
		for (int time = N; time >= 1; time--) { // 턴 
			boolean[][] visited = new boolean[N][M];
			
			for(int a = 0; a < ARCHER_NUMBER; a++) { // 아처 수만큼 반복
				int archerCol = archer[a]; // 아처 열 위치
				int minDistance = Integer.MAX_VALUE; // 최소 거리
				int minDistanceRow = Integer.MAX_VALUE; // 최소 거리의 행 좌표
				int minDistanceCol = Integer.MAX_VALUE; // 최소 거리의 열 좌표
				
				// 맵 탐색  (좌 하 -> 우 상(최대거리까지 탐색))
				for (int r = time-1; r >= (r-D < 0 ? 0: r-D) ; r--) {
					for (int c = 0; c < M; c++) {
						if (copyMap[r][c] == 1) { // 적이 있다면 
                        // 현재 거리보다 더 짧은 거리를 탐색했을 경우 최단 거리를 업데이트
							if (minDistance >= calcDistance(r, c, time, archerCol)) { 
								if (minDistance > calcDistance(r, c, time, archerCol)) {
									minDistance = calcDistance(r, c, time, archerCol);
									minDistanceRow = r;
									minDistanceCol = c;
								} else {
    // 최소 거리와 현재 탐색한 위치가 최소 거리가 같을 경우 탐색 위치가 최소거리의 열 좌표보다 왼쪽 인지 검사.
									if (minDistanceCol > c) { 
										minDistanceRow = r;
										minDistanceCol = c;
									}
								}
							}
						}
						
					}
				}
				if (minDistance <= D) visited[minDistanceRow][minDistanceCol] = true;
			}
			caseResult += countKill(copyMap, visited, time);
		}
		killEnemyNumber = Math.max(killEnemyNumber, caseResult);
	}
	
	public static int countKill(int[][] copyMap, boolean[][] visited, int time) {
		int res = 0;
		for(int r = 0; r < time; r++) {
			for (int c = 0; c < M; c++) {
				if(visited[r][c]) {
					copyMap[r][c] = 0;
					res++;
				}
			}
		}
		return res;
	}
	
	public static int calcDistance(int r1, int c1, int r2, int c2) {
		return Math.abs(r1 - r2) + Math.abs(c1 - c2);
	}
	
	public static void comb(int cnt, int start) {
		if(cnt == ARCHER_NUMBER) {
			solution();
			return;
		}
		for (int i = start; i < M; i++) {
			archer[cnt] = i;
			comb(cnt+1, i+1);
		}
	}
	
	public static int[][] copyMap() {
		int[][] temp = new int[N][M];
		for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) temp[i][j] = map[i][j];
		return temp;
	}

	public static void inputData() throws IOException {
		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+1][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());
		}
	}
}