백준 15686 치킨 배달

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

15686번: 치킨 배달

• 치킨집을 선택, 재귀를 사용
• 집에서 선택한 치킨집 중에서 거리가 최소인 것을 선택
• 위 에서 구한 거리를 모두 더한다

/*
	치킨집을 m개 만큼 선택
	각 집에서 치킨집을 선택
	거리의 최솟값

	main
		입력
	sol(index, cnt)
		if cnt == M
			for 집 갯수
				각 집에서 치킨집까지의 거리중 가장 작은 값 ret에 더함
			ans <- ret최솟값
			return
		pick_shop.push_back
		sol(index+1, cnt+1)
		pick_shop.pop_back
		sol(index+1, cnt)
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int map[50][50];
vector<pair<int,int>> house;
vector<pair<int, int>> shop;
vector<pair<int, int>> shop_pick;
const int INF= 987654321;
int ans = INF;
void sol(int index, int cnt)
{
	if (cnt == M)
	{
		int ret = 0;
		for (int i = 0; i < house.size(); i++)
		{
			int dist = 999;
			for (int j = 0; j < shop_pick.size(); j++)
			{
				int tmp = abs(shop_pick[j].first - house[i].first) + abs(shop_pick[j].second - house[i].second);
				dist = min(dist, tmp);
			}
			ret += dist;
		}
		ans = min(ret, ans);
		return;
	}
	if (index >= shop.size())
	{
		return;
	}
	shop_pick.push_back(shop[index]);
	sol(index + 1, cnt + 1);
	shop_pick.pop_back();
	sol(index + 1, cnt);
}
int main() {
	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) house.push_back({ i,j });
			else if (map[i][j] == 2) shop.push_back({ i,j });
		}
	}
	sol(0,0);
	cout << ans;
}