[BOJ] 17135. 캐슬 디펜스

조합과 BFS를 이용하여 반복하는 문제이다.

이 문제는 조합을 이용하여 궁수의 위치 3가지를 뽑고, 그 위치에서 BFS를 이용하여 거리 D안에 있는 적들을 PriorityQueue에 집어 넣어 계속 쳐치해가며 map상에 모든 적이 사라질때의 count 값의 최대값을 출력해주는 방식으로 해결하였다.

구현이 어렵지는 않으나 조건이 많으므로 천천히 하나하나 구현하는 것이 필요한 문제이다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_17135_캐슬디펜스 {
    static int[] di= {-1,0,0};
    static int[] dj= {0,1,-1};
    
    static int[][] mapOriginal;
    static int[][] mapTest;
    static boolean[][] visitForBFS;
    
    static int[] index;
    static int[] picks;
    static boolean[] visitForComb;
    
    static Queue<Pos> queue;
    static PriorityQueue<Pos> pq;
    
    static int answer;
    static int count;
    
    static class Pos implements Comparable<Pos>{
        int i,j,distance;
        Pos(int i,int j,int d){
            this.i=i;this.j=j;distance=d;
        }
        @Override
        public int compareTo(Pos o) {
            if(distance==o.distance)
                return Integer.compare(j, o.j);
            
            return Integer.compare(distance, o.distance);
        }
    }
    
    static int R,C,D;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        D=Integer.parseInt(st.nextToken());
        
        
        mapTest=new int[R+1][C];
        mapOriginal=new int[R][C];
        
        for(int i=0;i<R;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<C;j++) {
                mapOriginal[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        
        index=new int[C];
        for(int i=0;i<C;i++)
            index[i]=i;
        picks=new int[3];
        visitForComb=new boolean[C];
        
        answer=0;
        comb(0,0);
        System.out.println(answer);
    }
    
    static void comb(int start,int depth) {
        if(depth==3) {
            mapCopy();
            for(int i:picks) {
//                System.out.print("pick ==" + i+" ");
                mapTest[R][i]=2;
                
            }
//            System.out.println();
            count=0;
            bfs();
//            System.out.println(count);
            answer=Integer.max(answer, count);
            return;
        }
        
        for(int i=start;i<C;i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                picks[depth]=index[i];
                comb(i,depth+1);
                visitForComb[i]=false;
            }
        }
    }
    
    static void bfs() {
        queue=new LinkedList<>();
        
        while(true) {
            
            List<Pos> toKill=new ArrayList<>();
            
            
            
            for(int i=0;i<C;i++) {
                if(mapTest[R][i]==2) {    //궁수하나씩
                    pq=new PriorityQueue<>();
                    visitForBFS=new boolean[R+1][C];
                    queue.offer(new Pos(R, i, 0));
                    
                    while(!queue.isEmpty()) {
                        Pos cur=queue.poll();
                        
                        for(int dir=0;dir<3;dir++) {
                            int nextI=cur.i+di[dir];
                            int nextJ=cur.j+dj[dir];
                            
                            if(nextI<0 ||nextI>=R || nextJ<0 ||nextJ>=C)
                                continue;
                            
                            if(mapTest[nextI][nextJ]==0 && visitForBFS[nextI][nextJ]==false && cur.distance+1<=D) {
                                queue.offer(new Pos(nextI, nextJ, cur.distance+1));
                                visitForBFS[nextI][nextJ]=true;
                            }
                            
                            if(mapTest[nextI][nextJ]==1 && cur.distance+1<=D) {
                                pq.offer(new Pos(nextI, nextJ, cur.distance+1));
                            }
                        }
                    }
                    
                    if(!pq.isEmpty())
                        toKill.add(pq.poll());
                }
            }
            boolean go=false;
            for(int i=0;i<R;i++) {
                for(int j=0;j<C;j++) {
                    if(mapTest[i][j]!=0)
                        go=true;
                }
            }
            if(go==false)
                break;
            
            if(toKill.size()!=0) {
                for(Pos kill:toKill) {
//                    System.out.print(kill.i+","+kill.j+"  ");
                    if(mapTest[kill.i][kill.j]==1) {
                        count+=1;
                        mapTest[kill.i][kill.j]=0;
                    }
                }
//                System.out.println();
            }
            
            mapDown();
        }
    }
    
    static void mapCopy() {
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++)
                mapTest[i][j]=mapOriginal[i][j];
        }
        for(int i=0;i<C;i++) {
            mapTest[R][i]=-1;
        }
    }
    
    static void mapDown() {
        for(int i=R-2;i>=0;i--) {
            for(int j=0;j<C;j++) {
                mapTest[i+1][j]=mapTest[i][j];
            }
        }
        
        for(int i=0;i<C;i++) {
            mapTest[0][i]=0;
        }
    }
}