백준 15686 치킨배달

어떻게 하면 효율적으로 풀 수 있을까 치킨집 주위로 가까운집이 몇갠지 세서 통계내야하나 별 생각을 다하다가 결국 dfs를 이용해 완전탐색하기로 했다.

 

치킨집 조합을 모두 구해서 각 조합별 도시의 최소치킨거리를 구해 가장 작은 치킨거리를 보유한 조합을 선택한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n,m ;
int arr[51][51];
bool check[14];
int ans = 987654321;
vector<pair<int, int>> chicken;
vector<pair<int, int>> home;

int calc(pair<int,int> a, pair<int,int> b){
    return abs(a.first-b.first) + abs(a.second-b.second);
}

void DFS(int idx, int selected){

    
    if (selected == m) {
         int sum = 0;

         for (int i = 0; i < home.size(); i++){
             int dist = 987654321;
             for (int j = 0; j < chicken.size(); j++){

                 if (check[j]){
                     dist = min(dist, calc(home[i], chicken[j]));
                 }
             }
             sum += dist;

         }

         ans = min(ans, sum);

         return;

    }
    if (idx == chicken.size()){
        return;
    }
    check[idx] = true;
    DFS(idx + 1, selected + 1);
    check[idx] = false;
    DFS(idx + 1, selected);

}





int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    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] == 1){
                home.push_back(make_pair(i, j));
            } else if(arr[i][j] == 2){
                chicken.push_back(make_pair(i, j));
            }
        }
    }
    
    
    DFS(0,0);
    cout <<ans;
    
    return 0;
}