[백준 15686] 치킨 배달

1. 임의의 치킨집의 중 M개를 뽑기(조합)
2. M개의 치킨집에서 문제에 맞게 "치킨거리" 구하기
3. 완전탐색 진행
4. 해결!!!

#include <iostream>
#include <vector>
#include <cstring>
#define MAX_N 55
#define MAX_M 15

using namespace std;

struct Coord {
	int x;
	int y;
};

int N, M;
int MAP[MAX_N][MAX_M];
int used[MAX_M];
int min_dist;
vector<Coord> home;
vector<Coord> chicken;
vector<Coord> sample;
int my_min(int a, int b)
{
	return a < b ? a : b;
}

int get_abs(int r1)
{
	return r1 > 0 ? r1 : r1 * (-1);
}

int get_dist(int r1, int c1, int r2, int c2)
{
	return get_abs(r1 - r2) + get_abs(c1 - c2);
}

void get_sample(vector<Coord> sample, int m, int depth, int start) {
	if (depth >= m) 
	{
		// 거리 구하기
		int temp_sum = 0;
		for (int j = 0; j < home.size(); j++) 
		{
			int temp_dist = 2134567890;
			for (int i = 0; i < sample.size(); i++) 
			{
				temp_dist = my_min(temp_dist, get_dist(sample[i].x, sample[i].y, home[j].x, home[j].y));
			}
			temp_sum += temp_dist;
		}
		min_dist = my_min(min_dist, temp_sum);
		return;
	}
	for (int i = start; i < chicken.size(); i++) 
	{
		if (used[i] == 1) continue;
		sample.push_back(chicken[i]);
		used[i] = 1;
		get_sample(sample, m, depth + 1, i + 1);
		used[i] = 0;
		sample.pop_back();
	}
}

void CLEAR() {
	N = 0;
	M = 0;
	min_dist = 2134567890;
	home.clear();
	chicken.clear();
	memset(used, 0, sizeof(used));
	memset(MAP, 0, sizeof(MAP));
}

void INIT() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 1)
				home.push_back({ i, j });
			if (MAP[i][j] == 2)
				chicken.push_back({ i, j });
		}
	}
}

void SOLVE() {
	vector<Coord> sample;
	// M개의 치킨집 고르기
	get_sample(sample, M, 0, 0);
	cout << min_dist << endl;
}

int main() {
	CLEAR();
	INIT();
	SOLVE();
	int debug_point = 0;
	return 0;
}