1. 문제
17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
2. 풀이
static 변수
int N,M,D | 입력받은 값 |
int[] picked | 뽑은 궁수 위치 |
int[][] map | 입력받은 상태 |
int MAX | 최대값 |
Main
값을 입력받고 pick 메서드를 실행한다. 마지막에 MAX를 출력한다.
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(in.readLine());
for(int j=0;j<M;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
pick(0,0);
System.out.println(MAX);
}
궁수 뽑기
궁수 세 명의 위치를 뽑는다. 조합 코드를 활용했다.
3명을 다 뽑았다면 게임을 시작하고, 처치한 적의 수를 MAX값과 비교해 저장한다.
public static void pick(int cnt, int start){
if(cnt==3){
MAX = Math.max(MAX,game());
return;
}
for(int i=start;i<M;i++){
picked[cnt] = i;
pick(cnt+1, i+1);
}
}
게임 시작
상태를 저장할 status 배열을 생성한다.
적의 위치를 내리는 게 아니라 궁수의 위치(line)를 N부터 1까지 한 줄씩 올리는 방식으로 진행했다.
궁수 한 명씩 적을 공격한다. 거리가 가까운 적부터 처치해야하므로 1부터 D까지 순서대로 탐색한다.
만약 해당 거리 d에 있는 적을 처치했다면(>=0) count에 더하고 다음 궁수로 넘어간다.
public static int game(){
int count = 0;
int[][] status = new int[N][M];
for(int line = N;line>0;line--){
for(int pick:picked){
for(int d=1;d<=D;d++){
int cnt = attack(status,d,line,pick);
if(cnt<0) continue;
count+=cnt;
break;
}
}
}
return count;
}
거리별 공격 가능한지 체크
1. pick은 궁수의 위치 m열이다. pick-d부터 pick+d까지 탐색한다.
2. 적의 위치를 (nn,nm)이라고 할 때, nn은 d-(nm과 pick의 차이)를 line에서 빼면 된다.
3. 가능한 범위인지, 적이 있는지 파악한다.
4. status[nn][nm]이 0이면 아직 처치하지 않은 적이다. line을 저장하고 1을 반환한다.
5. line과 동일하다면 같은 턴에서 다른 궁수가 이미 처치한 적이다. 0을 반환한다.
탐색하면서 메서드가 끝나지 않았다면 -1을 반환한다.
public static int attack(int[][] status, int d, int line, int pick){
int nn;
for(int nm=pick-d;nm<=pick+d;nm++){
nn = line-(d-Math.abs(nm-pick));
if(nn<0 || nn >= line || nm <0 || nm >= M) continue;
if(map[nn][nm]==0) continue;
if(status[nn][nm] == 0){
status[nn][nm] = line;
return 1;
}else if(status[nn][nm] == line) return 0;
}
return -1;
}
전체 코드
import java.io.*;
import java.util.*;
public class BOJ_17135_캐슬디펜스 {
static int N,M,D;
static int[] picked = new int[3];
static int[][] map;
static int MAX = 0;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i=0;i<N;i++) {
st = new StringTokenizer(in.readLine());
for(int j=0;j<M;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
pick(0,0);
System.out.println(MAX);
}
public static void pick(int cnt, int start){
if(cnt==3){
MAX = Math.max(MAX,game());
return;
}
for(int i=start;i<M;i++){
picked[cnt] = i;
pick(cnt+1, i+1);
}
}
public static int game(){
int count = 0;
int[][] status = new int[N][M];
for(int line = N;line>0;line--){
for(int pick:picked){
for(int d=1;d<=D;d++){
int cnt = attack(status,d,line,pick);
if(cnt<0) continue;
count+=cnt;
break;
}
}
}
return count;
}
public static int attack(int[][] status, int d, int line, int pick){
int nn;
for(int nm=pick-d;nm<=pick+d;nm++){
nn = line-(d-Math.abs(nm-pick));
if(nn<0 || nn >= line || nm <0 || nm >= M) continue;
if(map[nn][nm]==0) continue;
if(status[nn][nm] == 0){
status[nn][nm] = line;
return 1;
}else if(status[nn][nm] == line) return 0;
}
return -1;
}
}
3. 결과
1년 전에는 deepcopy를 남발해서 메모리, 시간이 엄청나게 많이 걸렸다.
가까운 거리 별 탐색을 통해 최적화에 성공했다. ^__^
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 14888 연산자 끼워넣기 - JAVA (0) | 2023.05.25 |
---|---|
[BOJ] 17143 낚시왕 - JAVA (0) | 2023.05.24 |
[BOJ] 2947 나무조각 - JAVA (0) | 2023.05.22 |
[BOJ] 2839 설탕배달 - JAVA (1) | 2023.05.21 |
[BOJ] 2206 벽 부수고 이동하기 - JAVA (0) | 2023.05.21 |
댓글