(c++)백준 15686번: 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

[풀이]

치킨집 M개 조합을 구하여 각각 집에 대해 가장 작은 치킨거리를 더하는 문제였다.

처음에 치킨집 M개 위치를 dfs조합으로 구하고, bfs로 각 집에서 시작하여 가장 가까운 치킨집을 구하려고 했는데 시간초과가 나왔다.. 

알고보니 각각 집에 대해서 M개의 치킨집까지의 치킨거리를 모두 구하여 가장 작은 수를 더해주면 되는 거였다..!

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>//min
#include <cstring>//memset
#include <cmath>//abs
using namespace std;

struct Pos {
	int x, y;
};

int N, M;
bool check[13];
vector<Pos>House;//입력받은 집
vector<Pos>Pick;//선택받은 치킨집
vector<Pos>Chicken;//입력받은 치킨집
int Min = 987654321;


//M개 치킨집 조합 구하기
void getChicken(int x, int cnt) {
	if (cnt == M) {
		int res = 0;
		for (int i = 0; i < House.size(); i++) {
			int min_dist = 987654321;
			//각 집에서 가장 가까운 치킨집 찾기
			for (int j = 0; j < Pick.size(); j++) {
				min_dist = min(min_dist, abs(House[i].x - Pick[j].x) + abs(House[i].y - Pick[j].y));
			}
			res += min_dist;
		}
		Min = min(Min, res);
		return;
	}
	for (int i = x; i < Chicken.size(); i++) {
		if (check[i] == true)
			continue;
		check[i] = true;
		Pick.push_back({ Chicken[i].x,Chicken[i].y });
		getChicken(i, cnt + 1);
		check[i] = false;
		Pick.pop_back();
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int n;
			cin >> n;
			if (n == 1)
				House.push_back({ i,j });
			else if (n == 2)
				Chicken.push_back({ i,j });
		}
	}
	getChicken(0, 0);
	cout << Min << '\n';
	return 0;
}