BOJ_15686_치킨배달

[changicho]

link

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include<math.h>

using namespace std;

int map[51][51], N, M, answer = 50 * 100 * 50;

struct axis {
	int y, x;
};

struct home {
	int y, x;
	int distance[13];
};

vector<home> house;
vector<axis> chicken;
bool visited[13];

int get_distance(home h, axis a) {
	return abs(h.y - a.y) + abs(h.x - a.x);
}


void dfs(int depth, int count, int sum) {
	if (sum > answer) {
		return;
	}
	if (chicken.size() - count == M) {
		int new_answer = 0;
		for (home h : house) {
			int min_distance = h.distance[0];
			for (int i = 0; i < chicken.size(); i++) {
				min_distance = min(min_distance, h.distance[i]);
			}

			new_answer += min_distance;

			if (new_answer > answer) {
				return;
			}
		}
		//cout << new_answer << "\n";

		//for (bool b : visited) {
		//	cout << b;
		//}
		//cout << endl;
		answer = min(answer, new_answer);
		return;
	}

	visited[depth] = 1;
	dfs(depth + 1, count + 1);
	visited[depth] = 0;
	dfs(depth + 1, count);
}

void solution() {
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];

			switch (map[y][x])
			{
			case 1:
				home temp_home;
				temp_home.y = y;
				temp_home.x = x;
				house.push_back(temp_home);
				break;
			case 2:
				axis temp_axis;
				temp_axis.y = y;
				temp_axis.x = x;
				chicken.push_back(temp_axis);
				break;
			}
		}
	}

	// 모든 치킨집과의 거리 계산
	for (int home_index = 0; home_index < house.size(); home_index++) {
		for (int i = 0; i < chicken.size(); i++) {
			house[home_index].distance[i] = get_distance(house[home_index], chicken[i]);
		}
	}

	dfs(0, 0);

	cout << answer << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	solution();

	return 0;
}