[JAVA] 알고리즘 : DFS- 피자 배달 거리

import java.util.ArrayList;
import java.util.Scanner;

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

class Main{
    static int n, m, len, answer=Integer.MAX_VALUE;
    static int[] combi;
    static ArrayList<Point> hs, pz;
    public void DFS(int L, int s){
        if(L==m){ // m개 뽑았을 때
           /* for(int x:combi) System.out.print(x+" ");
            System.out.println();*/
            int sum = 0; // 도시의 피자 배달 거리
            for(Point h : hs){ // 집
                int dis = Integer.MAX_VALUE; // 집의 피자 배달 거리
                for(int i : combi){ // 피자 배달 거리(해당 집과 피자집들고의 거리 중 최소값) 계산
                    dis = Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y));
                }
                sum+=dis; // 각 집들의 피자 배달 거리 누적
            }
            answer=Math.min(answer, sum); // 조합의 경우의 수 중 도시의 최소 피자 배달 거리 찾기
        }
        else{
            for(int i=s; i<len; i++){
                combi[L]=i;
                DFS(L+1, i+1);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt(); // 살리는 피자집 개수
        pz=new ArrayList<>(); // 피자집 좌표들
        hs=new ArrayList<>(); // 집 좌표들
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int tmp=kb.nextInt();
                if(tmp==1) hs.add(new Point(i,j)); // 집
                else if(tmp==2) pz.add(new Point(i,j)); // 피자집
            }
        }
        len=pz.size(); // 피자집의 개수
        combi=new int[m]; // len개에서 m개를 뽑는 조합 (len C m)
        T.DFS(0,0);
        System.out.println(answer);
    }
}