[백준] 15686 치킨 배달

문제

N×N인 도시
도시의 치킨 거리는 모든 집의 치킨 거리의 합
치킨 거리 = (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|
치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하기

입력

N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집

출력

도시의 치킨 거리의 최솟값을 출력

풀이

최대 M개의 치킨집을 조합하여 최소 도시의 치킨 거리를 구해야함
-> 치킨집을 M개씩 조합하기
-> M개의 치킨집과의 치킨 거리 구한 후 최소값 찾기

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

using namespace std;

#define MAXN 51
int N, M, answer=1e9;
int graph[MAXN][MAXN];

vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<pair<int, int>> cal;

bool chickenCheck[14];
int distanceCalculate()
{
	int sum = 0;
	for (int i = 0; i < house.size(); i++)
	{
		int x = house[i].first;
		int y = house[i].second;
		int d = 1e9;

		for (int j = 0; j < cal.size(); j++)
		{
			int xx = cal[j].first;
			int yy = cal[j].second;
			int Dist = abs(xx - x) + abs(yy - y);

			d = min(d, Dist);
		}
		sum += d;
	}
	return sum;
}


void joinChicken(int index,int cnt) {
	
	if (cnt == M) { //치킨이 M개가 된 경우 치킨거리 합 구하기
		answer = min(answer, distanceCalculate()); 
		return;
	}

	for (int i = index; i < chicken.size(); i++) { //조합 -> 시작점=index
		if (chickenCheck[i] == true) continue;

		chickenCheck[i] = true;
		cal.push_back(chicken[i]);
		joinChicken(i, cnt +1);
		chickenCheck[i] = false;
		cal.pop_back();
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	int input;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> input;
			graph[i][j] = input;

			if (input == 1) {
				house.push_back({ i,j });
			}
			else if (input == 2) {
				chicken.push_back({ i,j });
			}

		}
	}

	joinChicken(0, 0);
	cout << answer;

	return 0;
}