[백준] 17135번 캐슬 디펜스 (gold 3

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    int v;
    public Point(int x,int y,int v){
        this.x=x;
        this.y=y;
        this.v=v;
    }
}
public class Main{
    static boolean[][] map; //맵 초기화
    static int n; //행
    static int m; //열
    static int d; //거리제한
    static boolean[] arrow; //궁수배치
    static ArrayList<Integer> arr; //선택궁수위치
    static int max=0; // 최댓값 비교하기.
    static int[] numx={-1,1,0,0}; //이동
    static int[] numy={0,0,-1,1}; //이동

    static Queue<Point> que=new LinkedList<>();
    public static void main(String[] args) throws IOException {

        input(); //입력받기
        back(0,1); //궁수배치하고, 배치결과에 따라 시행.
        System.out.println(max);

    }
    //맵 만들기.
    public static void input() throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.valueOf(st.nextToken());
        m=Integer.valueOf(st.nextToken());
        d=Integer.valueOf(st.nextToken());

        //맨 아랫줄은 성위치이므로 일단 만들어둠. 후에 궁수배치.
        map=new boolean[n+2][m+1];

        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                if(Integer.valueOf(st.nextToken())==1){
                    map[i][j]=true; //적은 true로 표시
                }
            }
        }

        //궁수 배치가능 배열
        arrow=new boolean[m+1];
    }

    //궁수 배치 백트래킹
    public static void back(int max, int index){
        if(max==3){
            arr=new ArrayList<>();
            for(int i=1; i<=m; i++){
                if(arrow[i]){
                    arr.add(i);
                }
            }
            simulation(); //함수 실행

            return;
        }

        for(int i=index; i<=m; i++ ){
            if(!arrow[i]){
                arrow[i]=true;
                back(max+1, i+1 );
            }
            arrow[i]=false;
        }

    }
    //시행하기.
    public static void simulation(){
        //맨아래 부터, 즉 n+1에서 행이 2일때까지 궁수를 전진시키면됨. 2다음턴엔 1로 가면
        //모든 적은 제외되게 되므로 의미x
        boolean[][] tMap=new boolean[n+2][m+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                tMap[i][j]=map[i][j];
            }
        }

        int enemy=0;

        for(int i=n+1; i>=2; i--){
            ArrayList<Point> del=new ArrayList<>();
            for(int j=0; j<3; j++){
                que.clear();
                //세 명의 궁수돌아가면서 가장 가까운 적 처치하기. 조건에따라서 우선순위큐 정렬기준 설정
                int bow=arr.get(j);
                boolean[][] visit=new boolean[n+2][m+1];

                //가장 작은 값 저장용. 만약 거리가 intermax이면 쏠 적이 없는 것.
                Point com=new Point(0,0,Integer.MAX_VALUE);

                visit[i][bow]=true;
                que.offer(new Point(bow, i, 0));

                while(!que.isEmpty()){
                    Point temp=que.poll();
                    //비교대상보다 거리 멀거나, 최대거리 초과이면 건너뜀
                    if(temp.v>d || temp.v>com.v){
                        continue;
                    }
                    //적일경우
                    else if(tMap[temp.y][temp.x]){
                        if(temp.v < com.v){
                            com.v=temp.v;
                            com.y=temp.y;
                            com.x=temp.x;
                        }
                        else if(temp.v==temp.v && temp.x < com.x){
                            com.x=temp.x;
                            com.y=temp.y;
                        }
                        continue; //이 후론 이보다 거리가 긴 케이스말고 존재x
                    }


                    for(int k=0; k<4; k++){
                        int tx=temp.x+numx[k];
                        int ty=temp.y+numy[k];

                        if(ty>=i || ty<1 || tx>m || tx<1 || visit[ty][tx]){
                            continue;
                        }
                        visit[ty][tx]=true;
                        que.offer(new Point(tx, ty, temp.v+1));
                    }
                }

                //만약 거리가 초기값 그대로면 적x
                if(com.v!=Integer.MAX_VALUE){
                    del.add(new Point(com.x, com.y, com.v)); //삭제할 적 추가.
                }
            }

            //추가된 적들 삭제하기. 삭제하면 tMap값 false로 바꾸어서 이중삭제막음.
            for(int j=0; j<del.size(); j++){
                Point temp=del.get(j);
                if(tMap[temp.y][temp.x]){
                    tMap[temp.y][temp.x]=false;
                    enemy++;
                }
            }
        }
        //max와 적 비교.
        max= max < enemy ? enemy : max;


    }


}