[BOJ] #15686 _ 치킨 배달

[치킨 배달] https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

dfs를 이용하여 M개의 치킨 집을 고르는 모든 경우의 수를 탐색한다.

모든 경우의 수 중 최소 거리를 구한다.

 

[ 소스 코드 ]

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define MAX_N 50
#define MAX_M 13

using namespace std;
int city[MAX_N + 1][MAX_N + 1] = { 0, }, sel[MAX_M + 1] = { 0, };
vector<pair<int, int> > chicken, house;
int n, m, min_dist = 999999;

int solve(int count, int current);
int calc_dist();
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &city[i][j]);
			if (city[i][j] == 1) house.push_back(make_pair(i, j));
			if (city[i][j] == 2) chicken.push_back(make_pair(i, j));
		}
	}

	solve(0, 0);
	printf("%d\n", min_dist);

	return 0;
}

int solve(int count, int current) {
	if (count == m) {
		min_dist = min(min_dist, calc_dist());
		return 0;
	}

	for (int i = current; i < chicken.size(); i++) {
		sel[count] = i;
		solve(count + 1, i + 1);
	}

	return 0;
}

int calc_dist() {
	vector<int> dist(house.size(), 999999);
	pair<int, int> c_tmp, h_tmp;
	int total_dist = 0;

	for (int i = 0; i < m; i++) {
		c_tmp = chicken[sel[i]];
		for (int j = 0; j < house.size(); j++) {
			h_tmp = house[j];
			dist[j] = min(dist[j], abs(c_tmp.first - h_tmp.first) + abs(c_tmp.second - h_tmp.second));
		}
	}
	for (int i = 0; i < house.size(); i++) total_dist += dist[i];

	return total_dist;
}