[c++] 백준 15686, 치킨 배달

백준 15686

🌲 문제 요약

집과 가장 가까운 치킨집 사이의 거리를 치킨 거리라 하며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합이라고 한다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시키려 할 때, 어떻게 고르면 도시의 치킨 거리가 가장 작게 될지 구하는 문제.

🌲 문제 풀이

집과 치킨집의 위치 정보를 각각 벡터 home과 chicken에 저장한 다음, 함수 combi를 이용하여 벡터 chickenList에 치킨집을 선택하는 경우의 수를 담는다.
이후 각각의 벡터들을 순회하며, 도시의 치킨 거리의 최솟값을 찾는다.

🌲 주의

combi 함수를 호출할 때, 인자 start의 값은 0이 아닌 -1이 되어야 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, m, a[55][55], ret = 987654321;
vector<pair<int, int>> home, chicken;
vector<vector<int>> chickenList;

void combi(int start, vector<int> v) {
	if (v.size() == m) {
		chickenList.push_back(v);
		return;
	}
	for (int i = start + 1; i < chicken.size(); i++) {
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
	return;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			if (a[i][j] == 1) {
				home.push_back({i, j});
			}
			else if (a[i][j] == 2) {
				chicken.push_back({i, j});
			}
		}
	}
	vector<int> v;
	combi(-1, v);
	
	for (vector<int> cList : chickenList) {
		int tmp = 0;
		for (pair<int, int> h : home) {
			int _dist = 1000;
			for (int c : cList) {
				int dist = abs(h.first - chicken[c].first) + abs(h.second - chicken[c].second);
				_dist = min(_dist, dist);
			}
			tmp += _dist;
		}
		ret = min(ret, tmp);
	}
	cout << ret << '\n';
	
	return 0;
}