BOJ - 17135 ) 캐슬디펜스

---

https://www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

---

N,M이 충분히 작기때문에 DFS로 상황을 만들고 정답이 될수있는지 구현하는 문제이다.

 

문제의 접근은 아래와 같이했다.

 

MAP을 입력받고, MAP의 맨 마지막줄 N+1번째에 궁수를 3명 배치해야한다.

 

궁수는 N개중 순서상관없이 3명을 뽑는 것이므로, 비트마스크를 통해서 2중 FOR문으로 조합의 경우의 수를 

 

뽑아낸후, MAP에 붙이고 계산하는 메소드에 넘겨준다.

 

입력으로 받은 D는 궁수가 공격을 할 수있는 최대거리이다. 

 

즉 한칸씩 내려오는 적들과의 좌표를 Math.abs(X2-X1)+Math.abs(Y2-Y1)으로 구하고 그값이 D보다 작거나

 

같으면 공격할 수 있다.

 

하지만 문제에서 궁수가 같은 타겟을 선택할 수있고, 한 궁수로부터 떨어진 거리가 같은 타겟이 여러개이면

 

가장왼쪽 ( ROW값에 상관없이 COL이 작은 좌표로 갱신 )의 타겟을 공격하는 것이다.

 

즉 선택되는 타겟에 대한 중복처리를 해주어야하고, 좌표도 갱신해야한다.

 

한턴이 끝나면 타겟들은 한칸씩 내려온다. 즉 Copy_map을 한칸씩내리며 갱신한다.

 

Copy_map이 전부 0 일때 ( N번이하 내려와서 적이 없을때) 처치한 타겟의 수를 리턴하면서 

 

가장 큰 값을 선택한다.

---

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M,D;
    static int map[][] = new int[20][20];
    static int copy_map[][] = new int[20][20];
    static boolean visit[][]= new boolean[20][20];
    static int answer = Integer.MIN_VALUE;
    public static void input() throws Exception{
        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());
        
        for(int y = 1 ; y <=N ; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x= 1 ; x <=M ; x++) {
                map[y][x]=Integer.parseInt(st.nextToken());
            }
        }
    }
    public static int pos_compute(int x1, int y1, int x2, int y2) {
        return Math.abs(x1-x2) + Math.abs(y1-y2);
    }
    
    
    public static void main(String[] args) throws Exception {
        input();
        // M개 중에 3개를 선택합니다.
        int archer[] = new int[M];
        for(int index = 7 , size = (1<<M) ; index < size ; index++) {
            int cnt =0;
            for(int j = 0 ; j < M; j++) {
                if((index & (1<<j)) !=0) {
                    cnt++;
                    archer[j] = 1;
                }
                else archer[j] = 0;
            }
            if(cnt ==3) {
                for(int i = 1; i <=M ; i++) copy_map[N+1][i] = archer[i-1];
                copy();
                answer = Math.max(answer, Compute());
            }
        }
        System.out.println(answer);
    }
    
    public static void copy() {
        for(int y = 1 ; y <=N ; y++) {
            for(int x = 1;  x<=M ; x++) {
                copy_map[y][x] = map[y][x];
            }
        }
    }
    public static int Compute() {
        int res =0;
        int bound =N-(D-1);
        while(check()) {
            for(int i = 1 ; i <=M ;i ++) {
        
                if(copy_map[N+1][i]==1) {
                    int min_ = Integer.MAX_VALUE;
                    int minlocal_x =M+1, minlocal_y =0 , len;
                    if(bound < 0 ) bound =1;
                    for(int y = N ; y >= bound ; y --) {
                        for(int x = 1 ; x <= M ; x++) {
                            if(copy_map[y][x] == 1) {
                                len =pos_compute(i, N+1, x, y);
                                if(len <= D) {
                                    if(min_ > len) {
                                            min_ = len;
                                            minlocal_x = x;
                                            minlocal_y = y;         
                                    
                                    }
                                    else if(min_ == len) {
                                        if(minlocal_x > x) {
                                            minlocal_x = x;
                                            minlocal_y = y; 
                                        }
                                    }
                                }
                            }
                        }            
                    }
                    visit[minlocal_y][minlocal_x] = true;
                }
            }
            for(int y = N ; y >= bound ; y --) {
                    for(int index = 1 ; index <=M ; index++) {
                        if(visit[y][index]){
                            visit[y][index] = false;
                            copy_map[y][index] = 0;
                            res++;
                    } 
                }
            }
            // 한줄씩 내려오고 처리를 해준다. 방문배열하고 , Map배열을 한칸씩 내려 준다.
            
            for(int y  = N ; y > 1 ; y--) {
                for(int x = 1 ; x <= M ; x++) {
                    copy_map[y][x] = copy_map[y-1][x];
                    visit[y][x] = visit[y-1][x];
                }
            }
            for(int index = 1 ; index <=M ; index++) copy_map[1][index] = 0;
        }
        return res;
    }
    public static boolean check() {
        for(int y = 1 ; y  <= N ; y++) {
            for(int x = 1 ; x <=M ; x++) {
                if(copy_map[y][x] ==1) return true;
            }
        }
        return false;
    }
 
}

---

---

 

제출했는데 자꾸 런타임 에러가 떠서 정리하려한다.

 

문제내에서 D가 배열의 범위를 넘은경우 D를 통한 타겟을 찾을떄 배열밖에 다가가게된다.

 

---

또한 백준이나 온라인저지사이트에 제출할때에 메소드의 선언은 PUBLIC으로 통일시켜줘야한다..

 

이클립스에 자동완성기능을 이용하면 Default가 Private이여서 한참 생각을 했던..