백준 15686 : 치킨 배달

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

1. 접근

• 결국엔 m개의 치킨집을 골랐을 때, 그때 각각의 집으로부터의 치킨집까지의 최소거리를 구하는 문제였다
• 원래는 DFS로 직접 조합을 구현하는 문제였지만 next_permutation에 중독된 나는 그냥 함수를 갖다써버렸다...
• DFS에서는 인자값으로 선택한 인자 개수와 현재 인덱스값을 넘긴다.
• 선택을 했는지, 하지 않았는지에 따라 재귀함수를 사용해서 구해주면 된다.
• 나의 경우, next_permutation 함수를 사용하여 m개를 선택하므로 m개의 1을 넣어주고, 나머지는 0으로 채워준 후 배열을 섞어주었다. 이때 1이면 거리를 구하는 방식으로 문제를 풀었다.

• 절댓값 차는 abs 함수를 사용하면 된다!

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> houses;
vector<pair<int, int>> stores;
int getdistance(pair<int, int> x, pair<int, int> y) {
	int ret = 0;
	if (x.first >= y.first)	ret += x.first - y.first;
	else ret += y.first - x.first;
	if (x.second >= y.second)	ret += x.second - y.second;
	else ret += y.second - x.second;

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tem = 0;
			cin >> tem;
			if (tem == 2)	stores.push_back(make_pair(i, j));
			else if (tem == 1)	houses.push_back(make_pair(i, j));
		}
	}

	vector<int> choice;
	for (int i = 0; i < stores.size() - m; i++) {
		choice.push_back(0);
	}
	for (int i = 0; i < m; i++) {
		choice.push_back(1);
	}

	int ret = -1;
	do{
		int tem = 0;
		for (int j = 0; j < houses.size(); j++) {
			int minval = -1;
			for (int i = 0; i < choice.size(); i++) {
				if (choice[i] == 1) {
					if (minval != -1)	minval = min(minval, getdistance(houses[j], stores[i]));
					else minval = getdistance(houses[j], stores[i]);
				}
			}
			tem += minval;
		}
		if (ret != -1)	ret = min(ret, tem);
		else ret = tem;
	} while (next_permutation(choice.begin(),choice.end()));

	cout << ret << "\n";
	return 0;
}

3. 다른 사람의 풀이

직접 DFS로 조합을 구하여 풀었다
https://jaimemin.tistory.com/1059