<백준> 15686

치킨 배달

문제

입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

int n, m;
int graph[50][50];
vector<pair<int, int>> houses;
vector<pair<int, int>> chicken;
bool visited[13];
int dist = MAX;

int GetDistance()
{
	int sum = 0;
	for (int i = 0; i < houses.size(); i++)
	{
		int minDist = MAX;
		int hx = houses[i].first;
		int hy = houses[i].second;

		for (int j = 0; j < chicken.size(); j++)
		{
			if (visited[j])
			{
				int cx = chicken[j].first;
				int cy = chicken[j].second;

				minDist = min(abs(hx - cx) + abs(hy - cy), minDist);
			}
		}
		sum += minDist;
	}
	return sum;
}

void DFS(int idx, int cnt)
{
	if (cnt == m)
	{
		dist = min(dist, GetDistance());
		return;
	}
	if (idx == chicken.size())
		return;

	visited[idx] = true;
	DFS(idx + 1, cnt + 1);
	visited[idx] = false;
	DFS(idx + 1, cnt);
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> graph[i][j];
			if (graph[i][j] == 1)
				houses.push_back({ i,j });
			if (graph[i][j] == 2)
				chicken.push_back({ i,j });
		}
	}

	DFS(0, 0);

	cout << dist;
}