백준 15686번 - 치킨 배달

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

DFS와 브루트포스를 이용하여 해결하는 문제다.

치킨집 중에서 DFS를 통해 M개의 치킨집 선택을 완료했다면

각각의 집에서 선택한 M개의 치킨집 사이의 거리중에 가장 가까운 거리를 구해준 뒤에

모든 집들의 치킨 거리의 합을 구해주면 된다.

다행히(?) 치킨집을 중복으로 선택하여 치킨 거리를 구해도 되기 때문에

별도의 예외처리없이 치킨 거리를 구해주면 된다.

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
#define inf 111111111;
 
int ans=-1;
int N,M;
vector<pair<int,int>> house; //집 좌표
vector<pair<int,int>> chicken; //치킨집 좌표
vector<int> inc; //치킨집 포함 유무
 
int solve(){
    
    int total_dist=0;
    for(int i=0;i<house.size();i++){
        
        int dist=inf;
        for(int j=0;j<chicken.size();j++){
            
            if(inc[j]==0)
                continue;
            
            dist=min(dist,abs(house[i].first-chicken[j].first)+abs(house[i].second-chicken[j].second));
        }
        
        total_dist+=dist;
    }
    
    return total_dist;
}
 
void dfs(int cnt,int pos){
    
    if(cnt==M){
        int dist=solve();
        ans=(ans==-1)? dist:min(ans,dist);
        return;
    }
    
    if(pos>=chicken.size())
        return;
    
    inc[pos]++;
    dfs(cnt+1,pos+1);
    
    inc[pos]--;
    dfs(cnt,pos+1);
    
}
 
int main(){
    
    int city=0;
    scanf("%d %d",&N,&M);
    for(int r=1;r<=N;r++){
        for(int c=1;c<=N;c++){
            scanf("%d",&city);
            if(city==1)    house.push_back(make_pair(r,c));
            if(city==2)    chicken.push_back(make_pair(r,c));
        }
    }
    
    inc=vector<int> (chicken.size(),0);
    dfs(0,0);
    
    cout<<ans<<endl;
    return 0;
}