BOJ) 캐슬 디펜스 (17135 번)

캐슬 디펜스

17135번: 캐슬 디펜스

생각보다 많이 어려웠던 문제였다.

적을 제거하는 규칙을 찾아 글로는 정리가 됐지만, 어떻게 코드로 구현해야할지 감이 오질 않았다.

그래서, 다른 블로그 글을 찾았고, 여기글을 많이 참고했다.

 

궁수가 적을 죽이는 순서는 삼각형을 그렸을 때, 좌측, 상단, 우측의 꼭지점 순서라고 생각하면 편하다.

 

공격 범위에 따라 위와 같은 순서로 적을 죽이게 된다.

범위 : 1 => y-1

범위 : 2 => (x-1,y-1) ~> (x, y-2) ~> (x+1, y-1)

이런 식으로 진행이 된다.

 

위에 언급한 블로그에서 dx와 dy를 어떤 순서로 검증해야하는지 참고했다.

반복문을 돌면서 공격범위에 따라 가장 좌측 x좌표부터 가장 우측 x좌표까지 탐색한다.

이 때, y는 x의 증가에 따라 -1을 해주다가(위쪽으로 올라가다가), 공격 범위가 넘어서면 +1을 해주며 위의 그림처럼 탐색을 하게했다.

 

또한, 처음에는 map 자체를 움직이려고 코드를 짰는데, 전체 map을 수정하는 작업이 불필요하게 증가한다고 느껴졌고, 위의 블로그에서 궁수의 위치 자체를 올려주는 것으로 오버헤드를 확 줄인 것을 보았다.

n*m 회 작업을 => 3회로 줄여 효율적으로 탐색할 수 있어서 조금 감명받았다..

요즘 몇 문제씩 구현을 제대로 못하고 다른 블로그 글을 참고하는 경우가 있는게 조금 슬프다..ㅠㅠ

더 힘내보자 !!

 

 

코드

 

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

public class CastleDefence_17135 {
  static int n,m,d, answer;
  static char[][] map;

  static final int MAX_ARCHER =3, STEP =1;
  static final char NONE ='0', ENEMY ='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());
    map = new char[n][m];
    for(int i=0; i<n; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<m; j++) {
        map[i][j] = st.nextToken().charAt(0);
      }
    }

    br.close();
    solution();
  }

  private static void solution() {
    answer=0;
    setArcherPosition(0, new LinkedList<>());
    System.out.println(answer);
  }

  private static void setArcherPosition(int start, LinkedList<Pos> list) {
    if(list.size() == MAX_ARCHER) {
      countKillEnemies(list);
      return;
    }
    for(int i=start; i<m; i++) {
      list.offer(new Pos(i,n));
      setArcherPosition(i+1, list);
      list.pollLast();
    }
  }

  private static void countKillEnemies(LinkedList<Pos> list) {
    char[][] currentMap = copyMap();
    int turn =0;
    Pos[] archers = getArchers(list);
    boolean[][] isDead = new boolean[n][m];
    int count =0;

    while(turn++ <n) {
      Queue<Pos> deadQueue = new LinkedList<>();
      for(Pos archer : archers) {
        findEnemy:
        for(int dist=1; dist<=d; dist++) {
          int dx = -(dist-1);
          int dy = -1;
          for(int k=1; k<2*dist; k++) {
            int nx = archer.x + dx;
            int ny = archer.y + dy;

            if(isInRange(nx,ny) && currentMap[ny][nx] == ENEMY) {
              if(!isDead[ny][nx]) {
                isDead[ny][nx] = true;
                deadQueue.offer(new Pos(nx, ny));
              }
              break findEnemy;
            }

            dx+= STEP;
            dy += k >=dist ? STEP : -STEP;
          }
        }
        archer.y-= STEP;
      }
      count += deadQueue.size();
      while(!deadQueue.isEmpty()){
        Pos dead = deadQueue.poll();
        currentMap[dead.y][dead.x] = NONE;
      }
    }
    answer = Math.max(answer, count);
  }

  private static boolean isInRange(int x, int y) {
    return x >=0 && x<m && y>=0;
  }

  private static Pos[] getArchers(LinkedList<Pos> list) {
    Pos[] archers = new Pos[MAX_ARCHER];
    for(int i=0; i<3; i++) {
      Pos archer = list.get(i);
      archers[i] = new Pos(archer.x, archer.y);
    }
    return archers;
  }

  private static char[][] copyMap() {
    char[][] copy = new char[n][m];
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        copy[i][j] = map[i][j];
      }
    }
    return copy;
  }

  private static class Pos {
    int x,y;
    public Pos(int x, int y) {
      this.x = x;
      this.y = y;
    }
    @Override
    public String toString() {
      return "x : " + x + "," + " y : " + y;
    }
  }
}