피자 배달거리(DFS 활용)

 

 

import java.util.*;

class Point{
    public int x, y;
    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){
        //조합이 한개 완성됐을 때
        //각 집의 피자배달 거리 구해서 더한 뒤 최솟값 구해야한다.
        //6개의 피자집 중 4개를 뽑는 15가지 경우가 들어간다.
        //combi에 들어감.(0,1,2,3 0,1,2,4 ...)
        if(L==m){
            int sum=0;
            for(Point h : hs){ //1개의 집 당 4개의 피자집과의 거리를 구한다.
                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));
                }
                // for문이 끝나면 해당 집의 최소 피자배달거리가 구해진다.
                sum+=dis;
            }
            //도시의 피자 배달 거리 중에서 제일 작은 값을 또 구한다.
            answer=Math.min(answer, sum);
        }
        else{//len개 중에서 m개 뽑기
            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];//lenCm 을 구한다.
        T.DFS(0, 0);
        System.out.println(answer);
    }
}