[boj17135 JAVA] 캐슬 디펜스
boj17135 문제링크
접근방법
- 문제 설명에서 궁수의 위치는 N+1에 위치하며 3명의 궁수를 배치한다라는 구문을보고 이부분은 조합으로 풀려고 생각했습니다. 최대 열이 15이므로 15C3 = 455로 크게 문제되지 않을 크기라고 생각했습니다.
- 조건을 잘걸어 재귀함수를 구현해 함수가 실행될때마다 궁수는 적을 선정하고 공격한 다음 그 후 적의 전진을 진행 시켜 풀이하겠다고 생각했습니다.
적을 선정하고 타격하는 함수 hunt()
적을 전진하는 함수 down()
궁수를 배치하는 함수 combi()
거리를 계산하는 함수 distance()
4가지를 사용해야겠다고 생각하고 문제를 풀었습니다.
느낀점
테스트케이스 6번을 틀려서 고치면 4번이 틀리는 상황이 연출됐는데
거리가 같을때를 정확히 지정해주지 않아서 이런 상황이 펼쳐졌는데..
거리가 기본값보다 작으면 교체하고 같을때는 y좌표를 확인해주는 방법으로 쉽게 해결했습니다.
처음 시작하기전에 골격을 잡고 갔다면 하지 않았을 실수였다고 생각합니다.
if(target[k].dist>check) {
target[k].dist = check;
target[k].x = i;
target[k].y = j;
}else if(target[k].dist==check) {
if(target[k].y > j) {
target[k].x = i;
target[k].y = j;
}
}
import java.io.*;
import java.util.*;
public class boj17135 {
static int row,col,dist,map[][],count,res,rest;
static boolean isSelected[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stz = new StringTokenizer(br.readLine()," ");
row = Integer.parseInt(stz.nextToken());
col = Integer.parseInt(stz.nextToken());
dist = Integer.parseInt(stz.nextToken());
map = new int[row+1][col];
isSelected = new boolean[col];
res =0;
for(int i=0;i<row;i++) {
stz = new StringTokenizer(br.readLine()," ");
for(int j=0;j<col;j++) {
map[i][j] = Integer.parseInt(stz.nextToken());
}
}
combi(0,0);
System.out.println(res);
}
static int temp[][],hunter[];
private static void combi(int idx,int cnt) {
if(cnt == 3) {
temp =new int[row+1][col];
hunter = new int[3];
int index =0;
for(int i=0;i<row+1;i++) System.arraycopy(map[i], 0, temp[i], 0, col);
for(int i=0;i<col;i++) {
if(isSelected[i]) {
hunter[index++]=i;
}
}
count= 0;
hunt();
res = Math.max(count, res);
return;
}
if(idx>=col) return;
isSelected[idx] =true;
combi(idx+1, cnt+1);
isSelected[idx] = false;
combi(idx+1, cnt);
}
private static void hunt() {
Data target[] = {new Data(100,100, Integer.MAX_VALUE)
,new Data(100,100, Integer.MAX_VALUE)
,new Data(100,100, Integer.MAX_VALUE)};
int check=0;
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++) {
if(temp[i][j]==1) {
for(int k=0;k<3;k++) {
check=distance(hunter[k],i,j);
if(check<=dist) {
if(target[k].dist>check) {
target[k].dist = check;
target[k].x = i;
target[k].y = j;
}else if(target[k].dist==check) {
if(target[k].y > j) {
target[k].x = i;
target[k].y = j;
}
}
}
}
}
}
}
for(int i=0;i<3;i++) {
if(target[i].x == 100 || target[i].y==100) continue;
if(temp[target[i].x][target[i].y] ==1) {
temp[target[i].x][target[i].y] = 0 ;
count++;
}
}
if(down()) {
hunt();
}else return;
}
private static boolean down() {
rest =0;
for(int i=row-2;i>=0;i--) {
for(int j=0;j<col;j++) {
temp[i+1][j] = temp[i][j];
}
}
for(int j=0;j<col;j++)temp[0][j] = 0;
for(int i=1;i<row;i++) {
for(int j=0;j<col;j++) {
if(temp[i][j]==1) rest++;
}
}
if(rest==0) return false;
else return true;
}
private static int distance(int y1, int x2, int y2) {
return Math.abs(row-x2)+Math.abs(y1-y2);
}
static class Data{
int x;
int y;
int dist;
public Data(int x, int y, int dist) {
super();
this.x = x;
this.y = y;
this.dist = dist;
}
}
}
Author And Source
이 문제에 관하여([boj17135 JAVA] 캐슬 디펜스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@952hi/boj17135-JAVA-캐슬-디펜스저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)