BJ17135 캐슬 디펜스
https://www.acmicpc.net/problem/17135
요구하는 조건을 구현할 수 있는 지를 확인하는 문제이다.
완전탐색을 이용해 확인하는 방식으로 해결했다.
세 궁수의 자리를 배치하기 위해 조합을 이용했고,
attack()
selectTarget()
eraseMonster()
moveDown()
와 같은 필요한 함수를 구현해 사용했다.
package day0408;
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;
//https://www.acmicpc.net/problem/17135
public class CastleDefense {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int N, M, D, numofM = 0, tnumofM, max = 0, numofKill;
static int[] numbers;
static int[][] map;
static int[][] tmpmap;
static int[][] dir = { { 0, -1, 0 }, { -1, 0, 1 } }; // 좌 상 우만 필요.
static void func(int cnt, int start) {
if (cnt == 3) {
tnumofM = numofM;
numofKill = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tmpmap[i][j] = map[i][j];
}
}
attack();
if(numofKill > max) max = numofKill;
return;
}
for (int i = start; i < M; i++) {
numbers[cnt] = i;
func(cnt + 1, i + 1);
}
}
static void attack() {
while (tnumofM > 0) {
for (int i = 0; i < 3; i++) {
selectTarget(i);
}
eraseMonster();
moveDown();
}
}
static void selectTarget(int bow) {
int startX = N - 1;
int startY = numbers[bow];
int startDist = 1;
Queue<int[]> q = new LinkedList<>();
q.add(new int[] { startX, startY, startDist });
while (!q.isEmpty()) {
int[] cur = q.poll();
if (tmpmap[cur[0]][cur[1]] >= 1) { // 가장가까운몬스터 ++한 후 리턴.
tmpmap[cur[0]][cur[1]]++;
return;
}
for (int d = 0; d < 3; d++) {
int nx = cur[0] + dir[0][d];
int ny = cur[1] + dir[1][d];
int dist = cur[2];
if (nx < 0 || nx >= N || ny < 0 || ny >= M || dist + 1 > D)
continue;
q.add(new int[] {nx, ny, dist + 1});
}
}
}
static void eraseMonster() {
//System.out.println(Arrays.toString(numbers));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
//System.out.print(tmpmap[i][j] + " ");
if (tmpmap[i][j] > 1) {
tnumofM--;
numofKill++;
tmpmap[i][j] = 0;
}
}
//System.out.println();
}
//System.out.println(numofKill);
}
static void moveDown() {
for (int i = N - 1; i >= 0; i--) { // 역순으로 해줘야 덮어쓰지않을듯.
for (int j = 0; j < M; j++) {
if (tmpmap[i][j] == 1) {
tmpmap[i][j] = 0;
if (i + 1 < N) {
tmpmap[i + 1][j] = 1;
}
if(i + 1 == N) {
tnumofM--;
}
}
}
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
numbers = new int[3];
map = new int[N][M];
tmpmap = 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());
if (map[i][j] == 1) {
numofM++;
}
}
}
func(0, 0);
bw.append(max + "");
bw.flush();
}
}
Author And Source
이 문제에 관하여(BJ17135 캐슬 디펜스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ17135-캐슬-디펜스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)