백준 치킨배달 C++

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

15686번: 치킨 배달

---

N*N의 도시가 있고, 도시의 각 칸이 치킨집,집,빈 공간입니다. (각각 2,1,0) .

이떄 M이 주어졌을 떄, 치킨집 중 최대 M개의 치킨집을 고르고 나머지 치킨 집을 패쇄해야 합니다.

C++의 next_permutation이 생각이 났고 ,전체 치킨 집 중 M개 뽑기를 next_permutation으로 구현하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define MAX_DISTANCE 987654321
 
using namespace std;
 
struct dataset{
    int x;
    int y;
    int number;
};
 
int ans = MAX_DISTANCE;
int n,m;
int arr[51][51];
int numof_chicken = 0;
 
vector<struct dataset> chicken; 
vector<int> combination;
vector<struct dataset> getRandomChicken;
vector<pair<int,int>> house;
 
void getInput(){
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> arr[i][j];
            if(arr[i][j] == 2){
               struct dataset temp_data;
               temp_data.x = i+1;
               temp_data.y = j+1;
               temp_data.number = numof_chicken;
               chicken.push_back(temp_data);
               numof_chicken += 1;
            }
            else if(arr[i][j] == 1){
                house.push_back({i+1,j+1});
            }
        }
    }
 
}
 
void setCombinate(){
    for(int i = 0;i<m;i++){
        combination.push_back(1);
    }
    for(int i = 0;i<numof_chicken - m;i++){
        combination.push_back(0);
    }
    sort(combination.begin(),combination.end());
}
 
void Init(){
    setCombinate();
}
 
void setRandomChicken(){
    getRandomChicken.clear();
}
 
int getDistance(int housex,int housey,int chickenx,int chickeny){
    return abs(housex-chickenx) + abs(housey-chickeny);
}
 
int CalculateDistance(){
    int totalDistance = 0;
    for(int i = 0;i<house.size();i++){
        int temp_distance = MAX_DISTANCE;
        for(int j = 0;j<getRandomChicken.size();j++){
            temp_distance =  min(getDistance(house[i].first,house[i].second,getRandomChicken[j].x,
            getRandomChicken[j].y),temp_distance);
        }
        totalDistance += temp_distance;
    }
 
    return totalDistance;
}
 
 
 
void pickChicken(){
    do{
        setRandomChicken();
        for(int i = 0;i<numof_chicken;i++){
            if(combination[i] == 1){
                getRandomChicken.push_back(chicken[i]);
            }
        }
       
        ans = min(ans,CalculateDistance());
    }while(next_permutation(combination.begin(),combination.end()));
}
 
int main(void){
    getInput();
    Init();
    pickChicken();
    cout << ans;
 
}