[BOJ] 15686. 치킨 배달

#include<iostream>
#include<vector>
#include<algorithm>
#define p pair<int,int>
using namespace std;

int n,m;
int map[50][50];
int ans;
int dp[2500][13];

vector<p> house;
vector<p> chicken;
vector<int> pick_idx;

void cal_dist(){
    int sum =0;
    
    for(int i=0; i<house.size(); i++){
        int pivot = 2e9;
        for(int j=0; j<m; j++){
            pivot = pivot < dp[i][ pick_idx[j] ] ? pivot : dp[i][ pick_idx[j] ] ;
        }
        sum += pivot;
    }
    ans = ans < sum ? ans : sum;
}

void dfs(int idx, int pick_cnt){
    if(pick_cnt == m){
        cal_dist();
        return ;
    }
    
    if( idx == chicken.size()){
        return ;
    }
    
    // pick
    pick_idx.push_back(idx);
    dfs( idx + 1, pick_cnt + 1 );
    pick_idx.pop_back();
    
    // pass
    dfs( idx+1, pick_cnt) ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ans = 2e9;
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
            if(map[i][j] == 1)
                house.push_back(p(i,j));
            else if(map[i][j] == 2)
                chicken.push_back(p(i,j));
        }
    }
    
    for(int i=0; i<house.size(); i++){
        for(int j=0; j<chicken.size(); j++){
            int _sum = 0;
            _sum += abs(house[i].first - chicken[j].first);
            _sum += abs(house[i].second - chicken[j].second);
                dp[i][j] = _sum;
        }
    }
    
    dfs(0,0);
    cout << ans << endl;
    return 0;
}