[백준 15686] 치킨배달 (조합) (C/C++)

#include <stdio.h>
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
 
int map[60][60];
int N, M;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
vector<pair<int, int>> choice;
int Min = 9999999;
 
int check(pair<int, int> house, vector<pair<int, int>> choice)
{
    int dMin = 9999999;
    
    for(int i = 0; i < choice.size(); i++)
    {
        int d = abs(house.first - choice[i].first) + abs(house.second - choice[i].second);
        
        if(d < dMin)
        {
            dMin = d;
        }
    }
    
    return dMin;
}
 
void combination(int idx, int cnt)
{
    if(cnt == M)
    {
        int sum = 0;
        
        for(int i = 0; i < house.size(); i++)
        {
            sum += check(house[i], choice);    
        }
        
        if(sum < Min)
        {
            Min = sum;
        }
        
        return;
    }
    
    for(int i = idx; i < chicken.size(); i++)
    {
        choice.push_back({chicken[i].first, chicken[i].second});
        combination(i+1, cnt+1);
        choice.pop_back();
    }
}
 
int main(void)
{
//    freopen("B15686_input.txt", "r", stdin);
    
    scanf("%d %d", &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({i, j});
            }
            else if(map[i][j] == 2)
            {
                chicken.push_back({i, j});
            }
        }
    }
    
    combination(0, 0);
    
    printf("%d", Min);
    
    return 0;
}