[백준][java] 치킨 배달

import java.util.Scanner;

public class 치킨_배달 {

    private static int N, M;
    private static int[][] map;
    private static Point[] chicken;
    private static Point[] house;
    private static int[] result;
    private static int[][] distance;
    private static int answer = Integer.MAX_VALUE;
    private static int h_idx;
    private static int c_idx;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        map = new int[N][N];
        chicken = new Point[13];
        house = new Point[2 * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 0-빈칸 1-집 2-치킨집
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1) {
                    house[h_idx++] = new Point(i, j);
                } else if (map[i][j] == 2) {
                    chicken[c_idx++] = new Point(i, j);
                }
            }
        }

        // 각 집과 치킨집 사이의 거리를 미리 구해둔다
        distance = new int[h_idx][c_idx];
        for (int i = 0; i < h_idx; i++) {
            for (int j = 0; j < c_idx; j++) {
                distance[i][j] = Math.abs(house[i].r - chicken[j].r) 
                    + Math.abs(house[i].c - chicken[j].c);
            }
        }

        // 치킨집을 M개 고른다
        result = new int[M];
        selectChicken(0, 0);

        System.out.print(answer);
    }
    

    private static void selectChicken(int cnt, int idx) {
        if (cnt == M) {
            // 도시의 치킨 거리를 구한다
            answer = Integer.min(answer, calDist());
            return;
        }

        for (int i = idx; i < c_idx; i++) {
            result[cnt] = i;
            selectChicken(cnt + 1, i + 1);
        }
    }

    private static int calDist() {
        int sum = 0;
        
        for(int i = 0; i < h_idx; i++) {
            int temp = Integer.MAX_VALUE;
            for(int j = 0; j < M; j++) {
                temp = Integer.min(temp, distance[i][result[j]]);
            }
            sum += temp;
        }
        
        return sum;
    }

    private static class Point {
        int r;
        int c;
        
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}