백준알고리즘
치킨배달
먼지의삶
2019. 8. 2. 20:09
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
int map[50][50];
int ans = 100000;
int n, m;
vector<pair<int,int>> chick;
vector<pair<int, int>> home;
void go(){
vector<int> permu;
for(int i = 0; i < chick.size(); i++){
if(i < m)
permu.push_back(1);
else permu.push_back(0);
}
do{
int sumna = 0;
for(int i = 0; i < home.size(); i++){
int s = 10000;
for(int j = 0; j < chick.size(); j++){
if(permu[j] == 1){
int temp = abs(home[i].first - chick[j].first) + abs(home[i].second - chick[j].second);
s = s > temp ? temp : s;
}
}
sumna += s;
}
ans = ans < sumna ? ans:sumna;
}while(prev_permutation(permu.begin(), permu.end()));
}
int main(){
int chicken =0;
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] == 2){
chick.push_back(make_pair(i,j));
}
if(map[i][j] == 1){
home.push_back(make_pair(i,j));
}
}
}
go();
cout<<ans<<endl;
return 0;
}
벡터로, 좌표받아주고 조합으로 선택해서 최소값구하는 브루트포스 풀이