<Algorithm> 160. 캐슬디펜스(BJO)

1. 17135번 캐슬디펜스(BJO)

   사용 알고리즘 : 완전탐색 

• 꽤 오래걸려서 풀었다. 입력값을 디버그 하기 쉽지 않은 문제여서 테케가 다 맞으면 틀린부분을 찾기가 힘들었다. 

• 이럴때는 디버그 하지말고 천천히 로직에 문제를 찾아 봐야겠다. (물론 처음에 완벽하게 하는게 가장 중요한듯....)

• 왜그런지 모르겠는데 처음에 이문제를 그냥 BFS로 풀려고 하니 당연히 시간초과가 발생했다. (최대사거리가 10인데..)

• 문제를 풀때 조건들 하나하나를 확실하게 하고 코드를 짜야겠다. 

• 아쉬운건 속도가 좀 느린데 3중반복이 들어가서 그런것 같다. 속도를 줄일 수 있는 부분을 찾아 봐야겠다.

문제에 대한 접근&생각

1. 궁수는 3명이고 죽일수 있는 적의 최대값을 구해야함 -> 궁수자리 완전탐색!
2. 궁수는 사정거리 까지만 적을 죽일 수 있음 -> 탐색조건!
3. 적들이 앞으로 다가옴 -> 처리조건! -> 궁수위치를 올림
4. 궁수 여러명이 한명을 노릴 수 있음 -> 3명이 모두 화살을 쏜 뒤에 적 제거
5. 죽일수 있는 경우가 여러명일 경우 가까운 왼쪽 부터 처리 -> 우선순위 큐!

내 코드 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int n,m,d;
    static int[][] map,temp;
    static boolean[] arrow;
    static List<Pair> emen;
    static int res,total;
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        d = sc.nextInt();
        map = new int[n+1][m];
        temp = new int[n+1][m];
        arrow = new boolean[m];
        emen = new ArrayList<>();
        /******************************
         * 궁수가 있을 수 있는 위치를 완전탐색하여
         * 적을 죽일 수 있는 경우 중 최대를 구한다.
         *******************************/
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int elemnt= sc.nextInt();
                map[i][j] = elemnt; 
                temp[i][j] = elemnt;
                if(map[i][j] == elemnt) {
                    emen.add(new Pair(i, j, -1));
                    // 적 좌표 저장
                }
            }
        }
        res = 0;
        solve(0, 0);
        System.out.println(res);
    }
    private static void solve(int deep, int idx) {
        // 궁수의 위치 완전탐색   
        if(deep == 3) {
            clone(map, temp);
            attak();
            return;
        }
        
        for(int i = idx; i < m; i++) {
            if(!arrow[i]) {
                arrow[i] = true;
                solve(deep+1, i+1);
                arrow[i] = false;
            }
        }
    }
    private static void attak() {
        List<Pair> arrowlist = new ArrayList<>();
        
        for(int i = 0; i < m; i++) {
            if(arrow[i])
                arrowlist.add(new Pair(n, i, 0));
        }
        
        int line = n;
        
        total = 0;
        
        while(line > 0) {
            
            Queue<Pair> dead = new LinkedList<>();
            
            for(Pair aw : arrowlist) {
                PriorityQueue<Pair> pq = new PriorityQueue<>(Pair::compare);
                aw.x = line;
                // 궁수 라인 당기기
                
                int min = Integer.MAX_VALUE;
                for(Pair tg: emen) {
                    if(map[tg.x][tg.y] !=1) continue;
                    int dist = Math.abs(aw.x-tg.x)+Math.abs(aw.y-tg.y);
                        if(dist <= d && tg.x < aw.x && min>=dist) {
                            min= Math.min(min, dist);
                            pq.add(new Pair(tg.x, tg.y, dist));
                        }
                }
                
                if(!pq.isEmpty())
                    dead.add(pq.poll());
                // 가장 가깝고 왼쪽인 처음것
            }
            
            if(!dead.isEmpty()) {                
                dead.stream().filter(dd->map[dd.x][dd.y]==1)
                             .forEach(dd->{
                                 map[dd.x][dd.y] = 0;
                                 total++;
                             });
            }
            line--;
        }
        
        res = Math.max(res,total);
    }
    
    private static void clone(int[][] taget, int[][] origin) {
        for(int i = 0; i < n ; i++) {
            taget[i] = origin[i].clone();
        }
    }
    static class Pair{
        int x,y,dist;
 
        public Pair(int x, int y, int dist) {
            super();
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
        private static int compare(Pair o1,Pair o2) {
            if(o1.dist != o2.dist)
                return Integer.compare(o1.dist, o2.dist);
            else
                return Integer.compare(o1.y, o2.y);
        }
        @Override
        public String toString() {
            return "Pair [x=" + x + ", y=" + y + ", dist=" + dist + "]";
        }
    }
}
 

참고 & 출처