https://www.acmicpc.net/problem/15686

풀이

입력에 주어진 치킨집을 M개로 줄일때 최소 도시의 치킨거리 (집-치킨집 거리의 최소값들의 합) 을 구하는 문제

• 조합 combination (dfs)
• 최소거리의 합의 최소를 구하는 문제! 👉 어떤 치킨집이 없어지지 않고 선택되어 남아있는지에 따라 거리가 달라짐
  • 특정 집 - 치킨집의 최소 거리를 구해야함 (치킨거리)
  • 치킨거리 합의 최소값을 구해야함 (도시의 치킨거리)

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int ans = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[] selected;
    static class Chicken{
        int x, y;
        public Chicken(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static class House{
        int x, y;
        public House(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static ArrayList<Chicken> chickens = new ArrayList<>();
    static ArrayList<House> houses = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int n = Integer.parseInt(st.nextToken());
                map[i][j] = n;
                if(n == 1){
                    houses.add(new House(i, j));
                }
                if(n == 2){
                    chickens.add(new Chicken(i, j));
                }
            }
        }

        selected = new boolean[chickens.size()];
        dfs(0,0);
        System.out.print(ans);
    }

    static void dfs(int idx, int cnt){
        if(cnt == M){
            ans = Math.min(ans,distance());
            return;
        }

        for(int i = idx; i < chickens.size(); i++){

            if (selected[i]) continue;

            selected[i] = true;
            dfs(i + 1, cnt + 1);

            selected[i] = false;
        }
    }

    static int distance(){
        int sum = 0;
        for (House house : houses) {
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < chickens.size(); i++) {
                if (selected[i]) {
                    Chicken chicken = chickens.get(i);
                    int d = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);
                    min = Math.min(min, d);
                }
            }
            sum += min;
        }
        return sum;
    }
}