[백준/17135] 캐슬 디펜스 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/17135

• 분류 : Simulation, BFS

• 풀이 시간 : 2시간 30분

  문제 풀이 방이 방법은 잘 선택했지만 살짝 다른 길로 갔다 오느라 조금 오래 걸렸다..

  그래도 풀이 방법 안보고 혼자 스스로 끝까지 해내서 조금은 뿌듯..

문제 해설

1. NxM 크기의 격자판에 적 존재.
2. 1x1 칸에 적은 한명만 존재
3. N+1 칸에 궁수 3명 배치해서 적 죽이려 함
4. 각 턴마다 궁수는 하나의 적을 공격할 수 있음 + 모든 궁수는 동시에 적을 죽임
   1. 궁수 위치 기준, 거리가 D이하인 적 중에서 가장 가까운 적 죽임
      1. 궁수(r1, c1)와 적(r2, c2)의 거리 : |r1-r2| + |c1-c2|
   2. 궁수와의 거리가 동일한 적이 여러명이면 왼쪽 적부터 죽임
5. 궁수의 공격이 끝나면, 적은 한칸씩 아래로 이동
   1. 성이 있는 칸으로 이동하면 게임에서 제외 = 죽는거랑 동일
6. 게임 한번 당 궁수가 죽일 수 있는 적의 최개 수는?

Solution

풀이 접근 방법

1. 궁수 3명 배치 = 궁수 배치 위치를 조합으로 구함
2. 궁수 위치 기준, 거리가 D 이하인 적 중에서 가장 가까운 적 죽임
   1. 거리가 1인 위치에 적 있음= 궁수 바로 위 위치에 적이 있으면 죽임
   2. 거리가 1인 위치에 적 없음 = 거리 1인 곳부터 범위를 D까지 넓혀가며 적 탐색 = BFS
      1. 거리가 동일하면 왼쪽 적부터 죽여야하기 때문에 BFS 시, 왼쪽 좌표부터 큐에 넣음

정답 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static int N, M, D;
  static int[][] map;
  static int enemies;
  static int maxKill;
  // 같은 거리에 공격할 적이 많으면 가장 왼쪽에 있는 적부터 선택하기 위해
  // 왼 -> 위 -> 오른쪽 순서대로 탐색
  static int[] dx = { 0, -1, 0 }, dy = { -1, 0, 1 };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.valueOf(st.nextToken());
    M = Integer.valueOf(st.nextToken());
    D = Integer.valueOf(st.nextToken());
    enemies = 0;
    maxKill = Integer.MIN_VALUE;

    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.valueOf(st.nextToken());

        if (map[i][j] == 1) {
          enemies += 1;
        }
      }
    }

    // 궁수 위치 조합으로 뽑아서 게임 시작
    setArcher(new boolean[M], 0, 3);
    bw.write(maxKill + "\n");
    bw.flush();
    bw.close();
  }

  static void setArcher(boolean[] selected, int start, int pick) {
    if (pick == 0) {
      int[] archer = new int[3];
      int idx = 0;

      // 궁수가 있는 y 좌표 조합으로 구함
      for (int i = 0; i < M; i++) {
        if (selected[i])
          archer[idx++] = i;
      }

      // 게임 시작
      play(archer);
      return;
    }

    for (int i = start; i < M; i++) {
      selected[i] = true;
      setArcher(selected, i + 1, pick - 1);
      selected[i] = false;
    }
  }

  static void play(int[] archer) {
    int[][] playMap = copyMap();
    boolean[][] died;
    int totalKillCnt = 0;

    for (int turn = 0; turn < N; turn++) {
      // 하나의 적을 두명 이상의 궁수가 죽일 수 있으니(동시에 공격) 죽일 사람 표시하고 나중에 한꺼번에 죽임
      died = new boolean[N][M];

      // 1) 적 선택
      for (int y : archer) {

        // 1-1) 만약 거리가 1인 위치에 적이 존재하면 바로 선택
        if (playMap[N - 1][y] == 1) {
          died[N - 1][y] = true;
        } else {
          // 1-2) 거리가 1인 위치에서부터 거리 넓혀가면서 적 탐색
          searchBFS(new Point(N - 1, y), died, playMap);
        }

      }

      // 2) 적 죽이기
      int killCnt = kill(died, playMap);

      // 3) 몇명 죽였는지 기록
      totalKillCnt += killCnt;

      // 4) 적 이동
      move(playMap);
    }

    // 5) 해당 궁수 위치에 대한 최대 죽일 수 있는 적의 수 갱신
    maxKill = Math.max(maxKill, totalKillCnt);
    return;
  }

  static int[][] copyMap() {
    int[][] map2 = new int[N][M];

    for (int i = 0; i < N; i++) {
      System.arraycopy(map[i], 0, map2[i], 0, M);
    }

    return map2;
  }

  static void searchBFS(Point start, boolean[][] died, int[][] playMap) {
    Queue<Point> queue = new LinkedList<Point>();
    boolean[][] visited = new boolean[N][M];

    // 거리가 1인 좌표는 이미 탐색했으니 큐에 넣음
    queue.add(start);
    visited[start.x][start.y] = true;

    // 그 나머지 거리의 좌표 탐색
    for (int cnt = 1; cnt < D; cnt++) {
      int size = queue.size();

      // 새로 추가된 좌표만 탐색
      for (int j = 0; j < size; j++) {
        int px = queue.peek().x;
        int py = queue.poll().y;

        // 거리가 같으면
        for (int i = 0; i < 3; i++) {
          int nx = px + dx[i];
          int ny = py + dy[i];

          if (!isIn(nx, ny) || visited[nx][ny])
            continue;

          // 적 발견하면 죽인다고 표시하고 반환
          if (playMap[nx][ny] == 1) {
            died[nx][ny] = true;
            return;
          }

          // 적 발견하지 못하면 다음 거리 탐색 위해 큐에 넣음
          queue.add(new Point(nx, ny));
          visited[nx][ny] = true;
        }
      }
    }
  }

  static int kill(boolean[][] died, int[][] playMap) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (died[i][j]) {
          cnt++;
          playMap[i][j] = 0;
        }
      }
    }

    return cnt;
  }

  static void move(int[][] playMap) {
    // 밑에서부터 조회해서 한칸씩 내림
    for (int i = N - 1; i >= 0; i--) {
      for (int j = 0; j < M; j++) {
        if (playMap[i][j] == 1) {
          playMap[i][j] = 0;

          if (i + 1 < N)
            playMap[i + 1][j] = 1;
        }
      }
    }
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < M) {
      return true;
    }
    return false;
  }
}