[Gold III] 캐슬 디펜스 - 17135
성능 요약
메모리: 41344 KB, 시간: 220 ms
분류
너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션
제출 일자
2024년 2월 11일 17:00:14
문제 설명
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
입력
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
출력
첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.
접근 방법
1. N+1 위치에 아처 3명을 배치 시킨다는 것은 0 ~ M-1 위치 중 3곳을 뽑는 것이다. ( 조합 )
2. 거리가 D이하인 적을 찾으면서 가장 왼쪽인 적을 찾아준 뒤 -1로 갱신해준다. ( 같은 적을 공격할 수 있기 때문에)
3. 궁수들의 공격이 끝나면(턴을 마친다면) 적을 한칸씩 내리는 것이 아닌 아처의 위치를 한칸씩 위로 올려준다.
-> 아처를 기준으로 위 부분만 확인하고 적을 제거해주면 된다.
4. 만약 결과값이 N * 3(아처가 매턴 잡을 수 있는 적)이라면 출력 후 바로 종료한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, D, result;
static int[][] map;
static int[][] copyMap;
static int[] archer = new int[3];
// 상,좌,우
static int[] dirX = {-1, 0, 0};
static int[] dirY = {0, -1, 1};
public static void main(String[] args) 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());
copyMap = new int[N][M];
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());
}
}
combination(0, 0);
System.out.println(result);
}
// 아처가 위치할 수 있는 조합을 얻는 메서드
private static void combination(int depth, int at) {
// 조합을 다 찾았다면 copyMap을 복사 후 적을 제거하는 메서드 실행
if (depth == 3) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copyMap[i][j] = map[i][j];
}
}
// 적 제거
removeEnemy();
// result가 N * 3이라면 그게 최대값이기 때문에 종료
if(result == N * 3){
System.out.println(result);
System.exit(0);
}
return;
}
// at를 기점으로 출력 후 다음 위치 선정
for (int i = at; i < M; i++) {
archer[depth] = i;
combination(depth + 1, i + 1);
}
}
// 적을 제거하는 메서드
private static void removeEnemy() {
int turn = 0; // 현재 몇턴인지 나타내는 변수
int count = 0; // 제거한 적의 수를 나타내는 변수
// 나가는 종료: 적이 존재하지 않을 때 , N만큼 턴을 진행했을 때
boolean exit = false;
while (turn != N && !exit) {
// 아처가 N - turn을 통해서 한칸씩 올라감 -> 적이 한칸씩 내려오는 것과 같음
for (int i = 0; i < 3; i++) {
bfs(N - turn, archer[i]);
}
// 맵에 적이 존재하지 않는다면 종료
exit = true;
for (int i = N - turn - 1; i >= 0; i--) {
for (int j = 0; j < M; j++) {
// 사라진 적을 제거 해줌
if (copyMap[i][j] == -1) {
copyMap[i][j] = 0;
count++;
}
// 적이 존재한다면 exit는 false로 만듬
else if (copyMap[i][j] != 0) {
exit = false;
}
}
}
// 한턴 마칠 때마다 값 증가
turn++;
}
// result 값이 최대값이라면 갱신
if (result < count) result = count;
}
// 아처를 기점으로 가장 가깝거나 가까우면서 가장 왼쪽인 적 찾기
private static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
// 아처의 시작점,거리 삽입
queue.add(new int[]{x, y, 0});
// 방문 배열
boolean[][] visit = new boolean[N][M];
// 가장 가까운 값을 찾기위해서 MAX_VALUE 미리 삽입
int minDist = Integer.MAX_VALUE;
int minX = Integer.MAX_VALUE;
int minY = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
int cur[] = queue.poll();
// 상,좌,우만 확인하면 된다. -> 밑은 확인 할 필요 X
for (int i = 0; i < 3; i++) {
int nX = cur[0] + dirX[i]; // 다음 X
int nY = cur[1] + dirY[i]; // 다음 Y
int nextDist = cur[2] + 1; // 아처와의 거리
// 배열 범위 밖이거나 || 제한 거리 이상이거나 || 방문했다면 continue
if (nX < 0 || nX >= x || nY < 0 || nY >= M || nextDist > D || visit[nX][nY]) {
continue;
}
// 다음 위치 방문 처리 후 큐에 삽입
visit[nX][nY] = true;
queue.add(new int[]{nX, nY, nextDist});
// 적이 있다면
if (copyMap[nX][nY] != 0) {
// 최소거리라면 갱신
if (nextDist < minDist) {
minX = nX;
minY = nY;
minDist = nextDist;
}
// 만약 거리가 같다면 Y가 더 작은 값(더 왼쪽인 값)
else if (nextDist == minDist) {
if (nY < minY) {
minX = nX;
minY = nY;
}
}
}
}
}
// minX 혹은 minY가 최대값이라면 제거 할 적이 없는 것
if (minX == Integer.MAX_VALUE || minY == Integer.MAX_VALUE) {
return;
}
copyMap[minX][minY] = -1;
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 15683번 : 감시 Gold4(골드4) - JAVA[자바] (1) | 2024.02.12 |
---|---|
[백준] 16234번 : 인구 이동 Gold4(골드4) - JAVA[자바] (1) | 2024.02.11 |
[백준] 17281번 : ⚾︎ Gold4(골드4) - JAVA[자바] (1) | 2024.02.11 |
[백준] 1918번 : 후위 표기식 Gold2(골드2) - JAVA[자바] (1) | 2024.02.11 |
[백준] 16236번 : 아기 상어 Gold3(골드3) - JAVA[자바] (1) | 2024.02.10 |