13.치킨 배달

📍 문제 설명

 

💡 접근

강의에서 배웠던 피자 배달거리 문제와 똑같은 문제다.

처음에는 치킨집의 갯수 중에 1개,2개, .. 뽑는 것중 도시의 치킨 거리가 제일 작게 되는 갯수를 찾는 줄 알았다.

하지만 이미 폐업할 치킨집의 갯수는 정해져 있고(m) 어느 치킨집들이 선택이 되어 도시의 치킨 거리가 최소가 되는지 찾는 문제였다. 

 

조합 부분은 아래의 코드를 기억하자! chickenLen개 중에서 combi(m) 만큼 뽑는 조합을 찾는 메서드임

for(int i = s; i < chickenLen; i++) {
    combi[L] = i;
    solution(L+1,i+1);
}

👩‍💻 코드

import java.util.*;

public class Main {

    public static ArrayList<Point> chicken = new ArrayList<>();
    public static ArrayList<Point> house = new ArrayList<>();
    public static int[] combi;
    public static int n,m,chickenLen, answer = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        int[][] map = new int[n][n];
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = kb.nextInt();
                if(map[i][j] == 1) house.add(new Point(i,j));
                if(map[i][j] == 2) chicken.add(new Point(i,j));
            }
        }
        //치킨집의 총 갯수 중에 M개를 뽑아야하고 도시의 치킨거리를 계산해본다.
        chickenLen = chicken.size();
        //chickenLen C m 을 계산해야하므로 출력할 배열 선언
        combi = new int[m];
        solution(0,0);
        System.out.println(answer);

    }

    private static void solution(int L, int s) {
        //len개 중에 m개를 뽑는 조합이 완성됐으면 도시의 치킨거리를 구할 것.
        //도시의 치킨거리는 모든 집의 치킨거리의 합
        if(L == m){
            //모든 집의 치킨거리의 합
            int sum = 0;
            //모든 집에 대해서 뽑힌 모든 치킨거리를 계산한다.
            for(Point h : house) {
                int distance = Integer.MAX_VALUE;
                //한개의 집에 대해서 치킨거리를 구하기
                //치킨거리는 집과 가장 가까운 치킨집 사이의 거리이다.
                for(int i : combi) {
                    distance = Math.min(distance, Math.abs(h.x-chicken.get(i).x) + Math.abs(h.y-chicken.get(i).y));
                }
                sum += distance;
            }
            //조합들 중 도시의 치킨거리의 최솟값
            answer = Math.min(answer, sum);
        }
        //조합 뽑기
        else {
            for(int i = s; i < chickenLen; i++) {
                combi[L] = i;
                solution(L+1,i+1);
            }
        }
    }

    private static class Point {
        private int x;
        private int y;

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

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }

    }
}