[BOJ] 17135 캐슬디펜스 - JAVA

1. 문제

17135번: 캐슬 디펜스

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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를 남발해서 메모리, 시간이 엄청나게 많이 걸렸다.

가까운 거리 별 탐색을 통해 최적화에 성공했다. ^__^