[백준]15686_치킨 배달

Solved

✔ 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이고 동네의 치킨집 중 m개의 치킨집이 폐업해야 할 때, 도시의 치킨 거리가 최솟값이 되도록 하자.
✔ 풀이는 두 단계로 나뉘어진다.
1. dis\[집 번호]\[치킨집번호] = 그 집과 그 치킨집 사이의 거리 를 모든 집과 모든 치킨 집에 대해 setting 한다.
2. 모든 치킨집의 수 c 중 폐업해야 하는 치킨집의 수 m 개를 고를 cCm을 dfs+백트래킹으로 구한다.
3. 이 때 도시의 치킨 거리는 1에서 구한 값을 사용해 구할 수 있다. 가장 작은 도시의 치킨 거리가 나올 때마다 answer 변수를 업데이트 한다.

using namespace std;
#include <iostream>
#include <map>

int n, m, ans=0x3f3f3f3f;
int input[200][200], dis[200][200], arr[200], c, h;
bool visit[200];
map<int, pair<int, int>> chicken, home;


int ABS(int a, int b) {
	if (a < b)
		return b - a;
	else return a - b;
}


void setDis() {
	for (int i = 0; i < c; i++) {
		int cx = chicken[i].first;
		int cy = chicken[i].second;
		for (int j = 0; j < h; j++) {
			int hx = home[j].first;
			int hy = home[j].second;
			dis[i][j] = ABS(cx, hx) + ABS(cy, hy);
		}
	}
}

int getDis() {
	int sum=0, minValue;
	for (int j = 0; j < h; j++) { //j: 각 집 번호
		minValue = 0x3f3f3f3f;
		for (int i = 1; i <= m; i++) { //arr[i]: 선택도니 치킨집 번호
			minValue = min(minValue, dis[arr[i] - 1][j]);
		}
		sum += minValue;
	}
	return sum;
}

//aCb
void comb(int cnt) {
	if (cnt == m) {
		int curDis = getDis();
		if (curDis < ans) ans = curDis;
		return;
	}
	for (int i = arr[cnt] + 1; i <= c; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[cnt + 1] = i;
			comb(cnt + 1);
			visit[i] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> input[i][j];
			if (input[i][j] == 2) chicken[c++] = make_pair(i, j);
			else if (input[i][j] == 1) home[h++] = make_pair(i, j);
		}
	}

	setDis();
	comb(0);
	cout << ans << '\n';
}