백준 15686 치킨 배달

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

15686번: 치킨 배달

 

- 브루트포스 백트래킹 문제이다.

 

- 치킨집 최대 13개 중 M개를 고르는 경우의 수 중 최대값은 13C6이며, 해당 경우에 각 집마다 치킨집과의 거리를 구해야 하므로 시간복잡도 값은

13C6∗2∗50∗13=2230800 정도가 나온다.

 

- a벡터에 치킨집 m개의 좌표를 push 해 가면서 m개를 채우는 모든 경우의 수가 될 때 마다 치킨거리를 구하는 식으로 구현을 한다. 초기 도시의 정보를 입력 받을 때 b 벡터에 해당 도시의 모든 집 좌표들을 push하고, 치킨거리를 구할 때 이를 활용한다. c 벡터는 각 집의 치킨거리가 저장된다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int arr[51][51];
int chicken_x[51];
int chicken_y[51];
int answer = 2100000000;
int num_chicken;
vector<pair<int,int>> a; // m개의 치킨집의 좌표
vector<pair<int,int>> b; // 집의 좌표

void DFS(int cnt, int index) {
	if (cnt == m) { // m개의 치킨집 선택완료(vector a에 선택된 치킨집의 좌표 담겨있음)
		int temp = 0;
		vector<int> c(b.size(), 2100000000);
		for (int i = 0; i < m; i++) {
			int x = a[i].first;
			int y = a[i].second;
			for (int j = 0; j < b.size(); j++) {
				temp = abs(x - b[j].first) + abs(y - b[j].second);
				c[j] = min(c[j], temp);
			}
		}
		int temp_answer = 0;
		for (int i = 0; i < c.size(); i++) temp_answer += c[i];
		answer = min(answer, temp_answer);
		return;
	}
	for (int i = index; i < num_chicken; i++) {
		a.push_back({ chicken_x[i], chicken_y[i] });
		DFS(cnt + 1, i + 1);
		a.pop_back();
	}
}
int main() {
	int chicken_index = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) { // 집의 좌표 저장
				b.push_back({ i,j });
			}
			else if (arr[i][j] == 2) { // 치킨집 좌표 저장(배열)
				chicken_x[chicken_index] = i;
				chicken_y[chicken_index++] = j;
				num_chicken++;
			}
		}
	}
	DFS(0, 0);
	cout << answer;
	return 0;
}