백준 15686 C++

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

이 문제는 개인적으로 조합을 만들 수 있다면 그렇게 어려운 문제는 아닌거 같다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n, m;
//int village[55][55];
vector<pair<int, int>> chickenHouses;
vector<pair<int, int>> houses;
vector<pair<int, int>> selectedChickenHouses;
int result = 500000;

int chickenDistance()
{
	int dist = 0;
	for (int i = 0; i < houses.size(); i++) {
		int minDis = 500000;
		for (int j = 0; j < selectedChickenHouses.size(); j++) {
			int d = abs(houses[i].first - selectedChickenHouses[j].first) + abs(houses[i].second - selectedChickenHouses[j].second);
			minDis = min(minDis, d);
		}

		dist += minDis;
	}

	return dist;
}

void selectChickenHouse(int s)
{
	if (selectedChickenHouses.size() == m) {
		for (auto i : selectedChickenHouses) {
			//cout << i.first << " : " << i.second << "\n";
		}
		result = min(result, chickenDistance());
		//cout << "result: " << result << "\n";
		return;
	}

	for (int i = s; i < chickenHouses.size(); i++) {
		selectedChickenHouses.push_back(chickenHouses[i]);
		//cout << "push back y: " << chickenHouses[i].first << "   x: " << chickenHouses[i].second << "\n";
		selectChickenHouse(i + 1);
		selectedChickenHouses.pop_back();
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int a; cin >> a;
			//village[i][j] = a;
			if (a == 1) houses.push_back(make_pair(i, j));
			if (a == 2) chickenHouses.push_back(make_pair(i, j));
		}
	}

	selectChickenHouse(0);

	cout << result;
}