[BOJ] 15686 : 치킨 배달 - travelbeeee

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

---

[알고리즘풀이]

치킨집을 최대 M개 살릴 수 있고, 치킨집이 많으면 많을수록 집들과의 거리가 가까워지므로 우리는 최대가 아닌 그냥 M개의 치킨집을 살리면 된다. 따라서, 백트레킹을 이용해 가능한 모든 경우에 대해서 치킨집을 M개 뽑고 그때 모든 집들과의 거리를 구해 최솟값을 갱신해나가면 된다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int N, M, map[50][50], k, ans = 99999999;
vector<pair<int, int>> c;

int get_length(vector<int> v) {
	int A = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) {
				int m = 99999999;
				for (int k = 0; k < M; k++) {
					m = min(m, abs(c[v[k]].first - i) + abs(c[v[k]].second - j));
				}
				A += m;
			}
		}
	}
	return A;
}

void bt(vector<int> v, int last) {
	if (v.size() == M) {
		ans = min(ans, get_length(v));
		return;
	}
	for (int i = last + 1; i < c.size(); i++) {
		v.push_back(i);
		bt(v, i);
		v.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	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] == 2)
				c.push_back(make_pair(i, j));
		}

	k = c.size() + 1 - M;

	for (int i = 0; i < k ; i++) {
		vector<int> v;
		v.push_back(i);
		bt(v, i);
		v.pop_back();
	}

	cout << ans;
}

---