[백준 15686] 치킨 배달

문제
도시에서 치킨집을 최대 M개만 남기고 모두 폐업을 시키려고 한다.

집에서는 여러 개의 치킨집 중 거리가 가장 최소인 치킨집에서 시켜먹는다.
이때 최대 M개의 치킨집이 남아있을 때 집과 치킨 사이의 거리의 합이 최소가되는 거리가 무엇인지 구하라

입력
첫재 줄에 N(2이상 50이하)과 M(1이상 13이하)가 주어진다.
둘째 줄부터 N개의 줄에 도시의 정보가 입력되며 0은 빈 칸, 1은 집, 2는 치킨집이다.

출력
최대 M개가 남았을 때 최소 치킨거리를 출력한다.

---

이 문제에서 치킨 거리를 구하기위해서 집과 치킨의 위치정보가 필요하다. 

따라서 맵을 입력받을 때 집과 치킨의 위치 정보를 따로 저장해두도록한다.

 

이후 1~M개를 선택했을 때 나올 수 있는 조합을 백트래킹을 통해 구하고 선택했다면 치킨 거리를 구한다.

각각의 집에서 최소의 거리인 치킨거리를 구하여 이 치킨 거리를 모두 더한다음 최종해와 비교하도록한다.

 

지금 생각해보니 따로 맵에 대한 정보를 저장할 필요가 없었다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
using namespace std;

int N, M;
int city_map[51][51];
int answer = 100000000;
vector<pair<int, int>> store;
vector<pair<int, int>> home;
vector<pair<int, int>> pick;


void solve(int next, int topick) {
	if (pick.size() == topick) {
		int total = 0;
		for (int i = 0; i < home.size(); i++) {
			int dist = 999999999;
			for (int j = 0; j < pick.size(); j++) {
				int temp = abs(home[i].first - pick[j].first) + abs(home[i].second - pick[j].second);
				dist = min(dist, temp);
			}
			total += dist;
		}
		answer = min(answer, total);
	}

	for (int i = next; i < store.size(); i++) {
		pick.push_back(store[i]);
		solve(i + 1, topick);
		pick.pop_back();
	}
}
int main()
{
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> city_map[i][j];
			if (city_map[i][j] == 1)
				home.push_back({ i,j });
			else if (city_map[i][j] == 2)
				store.push_back({ i,j });
		}
	}

	for (int i = 1; i <= M; i++) {
		solve(0, i);
		pick.clear();
	}

	cout << answer << endl;
	return 0;
}