백준알고리즘

치킨배달

먼지의삶 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;



}

벡터로, 좌표받아주고 조합으로 선택해서 최소값구하는 브루트포스 풀이