[BOJ]백준 17135번: 캐슬디펜스(Java)/시뮬레이션

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

이전의 풀이와는 조금 달라진 점이 있어서 다시 포스팅한다.

2년전에도 조합 구할 때 bound를 M인데 N으로 써놓고 삽질했는데.............. 2년이 지나도 똑같다 ㅎㅎ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw;
    static int[][] map;
    static int n,m,d,ans;
    static ArrayList<Point> enemy=new ArrayList<>();

    public static class Point{
        int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void comb(int k,int dep,int[] arr) throws IOException {
        //궁수 3명을 조합하는 함수
        if(dep==3){
            int score=game(arr);    //3명을 고른 뒤 시뮬레이션
            ans=Math.max(score,ans);    //죽일 수 있는 최대 적 갱신
            return;
        }

        for (int i = k; i < m; i++) {
            arr[dep]=i;
            comb(i+1,dep+1,arr);
        }
    }

    static int distance(Point a,Point b){    //a에서 b까지의 거리를 구하는 메소드
        return Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
    }

    private static int game(int[] arr) {
        int row=n,cnt=0;
        boolean[] E=new boolean[enemy.size()];    //적의 처리 여부를 체크해주는 배열
        Arrays.fill(E,true);    //처음에는 전부 살아있는 것으로 초기화

        while(row>0){    //적이 아래로 내려오는 것을 궁수가 위로 올라가는 것으로 구현
            Point[] kill=new Point[3];    //각각의 궁수가 처리할 적의 좌표를 저장
                                          //저장해준 뒤 한꺼번에 처리하는 것이 아니라 그때그때 처리하면 오류 발생
            for (int i = 0; i < arr.length; i++) {
                int dist=d;        //최소 거리를 d로 초기화
                Point cur=new Point(arr[i],row);    //궁수의 현재 좌표
                kill[i]=new Point(m,-1);

                for (int j=0;j<E.length;j++) {
                    if(!E[j])continue;        //이미 해치운 적이라면 pass
                    Point e=enemy.get(j);        
                    int ad=distance(cur,e);        //궁수와 적 사이의 거리를 구함
                    if((ad==dist&&e.x<kill[i].x)||(ad<dist)){        //1. 거리가 같으면서 왼쪽에 있거나 2. 거리가 더 작으면
                        dist=distance(cur,e);        //최소 거리 및 좌표 갱신
                        kill[i]=e;
                    }
                }
            }

            row--;            //앞으로 이동
            for (int i = 0; i < E.length; i++) {
                for(int j=0;j<kill.length;j++){
                    if((kill[j].x==enemy.get(i).x)&&(kill[j].y==enemy.get(i).y)&&E[i]){
                        //kill배열에 미리 저장해두었던 좌표를 이미 처리했는지 고려하면서 카운트 
                        cnt++;
                        E[i]=false;
                    }
                }
                if(enemy.get(i).y==row){        //성에 다다른 적은 삭제
                    E[i]=false;
                }
            }

        }
        return cnt;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        d=Integer.parseInt(st.nextToken());

        map=new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]==1)enemy.add(new Point(j,i));    //적의 좌표를 ArrayList에 저장
            }
        }

        comb(0,0,new int[3]);

        bw.write(ans+"");

        br.close();
        bw.flush();
        bw.close();

    }
}