백준15686 치킨 배달 - C++

 

모든 집의 치킨 거리의 합이 가장 작게 되도록 치킨집 M 개를 고르면 된다.

 

조금 더 빠르게 하기 위해서 

각 집과 치킨집의 거리를 distmap [집][치킨집]으로 정해놓자.

이때 집과 치킨집을 지도에 직접 뿌릴 필요는 없다.

우리가 볼 건 지도를 직접 볼 필요가 없고

좌표만 가지고 계산하면 되기 때문이다.

 

그 후 완전 탐색을 이용하여 모든 경우의 수를 살핀다.

이 때 치킨집은 M개만 남기기 때문에 

M개를 고른 후 distmap을 순회하여 가장 작은 값만 남기고 

Min 값을 찾으면 된다.

 

집이 최대 2N = 100개고 치킨집이 M = 13 개 이므로 

경우의 수는 13C5 * 100 * 13 이므로 시간이 오래 걸리지 않는다.

#include <stdio.h>

int n,m;
int ch, h;//치킨집 개수, 집 개수
int distmap[101][14]; //특정 집 -> 치킨 집 거리 미리 계산
int chick_y[14];
int chick_x[14];
int home_y[101];
int home_x[101];
int Min = 987654321;
int selected[14];


int abs(int x) {
	if (x < 0) return -x;
	return x;
}
int dist(int h, int c) {
	return abs(chick_y[c] - home_y[h]) + abs(chick_x[c] - home_x[h]);
}

void calDist() {
	for (int h_num = 0; h_num < h; h_num++) {
		for (int c_num = 0; c_num < ch; c_num++) {
			distmap[h_num][c_num] = dist(h_num, c_num);
		}
	}
}

void select(int num, int idx) {
	if (num == m) {
		int tmp = 0;
		for (int i = 0; i < h; i++) {
			int tmpmin = 987654321;
			for (int j = 0; j < ch; j++) {
				if (selected[j]) {
					if (tmpmin > distmap[i][j]) tmpmin = distmap[i][j];
				}
			}
			tmp += tmpmin;
		}
		if (tmp < Min) Min = tmp;
		return;
	}
	for (int i = idx; i < ch; i++) {
		if (selected[i]) continue;
		selected[i] = 1;
		select(num + 1, i);
		selected[i] = 0;
	}

}

int solve() {
	calDist();
	//M개 골라서 최소거리찾기 (M개가 항상 최소 치킨 거리) 
	//쓸모없는 경우는 있어도 거리가 더 많은 경우는 없다.
	select(0,0);
	return Min;
}

int main() {
	scanf("%d %d", &n, &m);
	int tmp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &tmp);
			if (tmp == 2) {
				chick_y[ch] = i;
				chick_x[ch++] = j;
			}
			else if (tmp == 1) {
				home_y[h] = i;
				home_x[h++] = j;
			}
		}
	}
	int ans = solve();
	printf("%d\n", ans);
}