목표 : N*N형태의 지도에서 치킨집의 위치를 (cx,cy) 집의 위치를 (x,y)라고 했을 때 치킨집 중에서 |cx-x| + |cy-y| 거리가 최소인 값을 치킨 거리라고 한다. 각각의 집에서 치킨 거리의 합을 도시의 치킨 거리라고 한다. 최대 M개의 치킨 집만 남았을 때 도시의 치킨 거리의 최솟값을 구하자.
조건 : 1 <= N <= 50, 1 <= M <= 13, 1 <= 집의 개수 <= 2*N
각각의 집에서 치킨집까지의 거리들을 구한 뒤 M개의 치킨 집을 골라 도시의 치킨 거리의 최솟값을 구한다. M개의 치킨 집을 고른다면 M-1, M-2개의 치킨집을 골랐을 때의 치킨 거리를 이미 포함하므로 재귀 함수를 활용해 M개의 치킨집을 골랐을 때 도시의 치킨 거리를 비교해 답을 구한다.
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
int N, M, dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1}, ans = 987654321;
vector<pair<int,int>> chicken, home;
vector<int> dist[100];
vector<int> choose;
void dfs(int c){
if (choose.size() == M) {
int sum = 0;
for (int i = 0; i < home.size(); i++){
int tmp = 987654321;
for (int j = 0; j < choose.size(); j++){
if (tmp > dist[i][choose[j]]){
tmp = dist[i][choose[j]];
}
}
sum += tmp;
}
if (ans > sum){
ans = sum;
}
}
for (int i = c; i < chicken.size(); i++){
choose.push_back(i);
dfs(i+1);
choose.pop_back();
}
}
int main(){
scanf("%d%d",&N,&M);
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
int a;
scanf("%d",&a);
if (a == 1){
home.push_back({i,j});
}
else if (a == 2){
chicken.push_back({i,j});
}
}
}
for (int i = 0; i < home.size(); i++){
int nx = home[i].first, ny = home[i].second;
for (int j = 0; j < chicken.size(); j++){
int tx = chicken[j].first, ty = chicken[j].second;
int l = nx - tx, r = ny - ty;
if (l < 0){l *= -1; }
if (r < 0){r *= -1; }
dist[i].push_back({l+r});
}
}
dfs(0);
printf("%d\n",ans);
return 0;
}