피자 배달 거리

!문제 다시 풀어보기 9/3.. 

조합 만드는 방식은 외워두자..

 

피자집 ArrayList, 집위치 ArrayList를 만들고 피자집 m개를 고른 조합을 만든다

각 집까지의 최소 배달 거리를 sum에 누적해서 가장 작은 경우가 나오는 조합일때 정답

 

보드를 만드는게 아니라 입력 받을 때 피자집인지 가정집인지 판단해서 ArrayList에 넣는다

DFS에서는 만든 조합으로 가정집을 각각 돌면서 한 가정집까지 가는 최소거리를 구하고 그걸 sum에 누적한다

 

전체 코드

import java.util.*;

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

class Main{


    static int[] comb; //조합 저장용 배열
    static ArrayList<point> pz, hs;

    static int n, m, ans = Integer.MAX_VALUE, len;

    public void DFS(int L, int s){
        if (L == m){
            int sum = 0;
            for (point h : hs){ // 집을 순회하면서
                int dis = Integer.MAX_VALUE;
                for (int i : comb) { //피자집의 조합을 순회하면서 h번째 집에 도달하는 최소거리 구하기
                    dis = Math.min(dis, Math.abs(h.x - pz.get(i).x) + Math.abs(h.y - pz.get(i).y));
                }
                //sum에 각 집에 도달하는 최소거리를 누적
                sum += dis;
            }
            ans = Math.min(ans, sum);
        }

        else {
            for (int i = s; i < len; i++){
                comb[L] = i;
                DFS(L+1, i+1);
            }
        }
    }


    public static void main(String[] args) {
        //피자배달거리는 가능한 배달 거리중 가장 큰거일거같음
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        pz = new ArrayList<>();
        hs = new ArrayList<>();

        //따로 보드를 만들고 보드를 순회하는 것이 아니라 피자집과 집 ArrayList에 좌표를 넣어준다
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                int tmp = in.nextInt();
                if (tmp == 1) hs.add(new point (i,j));
                else if (tmp == 2) { pz.add(new point(i,j));
                }
            }
        }

        len = pz.size(); // 피자집의 갯수로 len C comb, 전체 피자집 중에서 m개를 구하는 조합
        comb = new int[m]; // 조합은 피자집 m개의 최소배달거리를 구함
        T.DFS(0,0);
        System.out.println(ans);
    }
}