백준 15686 치킨 배달

BOJ 15686

목표 : 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;
}