문제: BOJ 15686 — 치킨 배달 · English · 日本語
도시에는 집 H개와 치킨집 C개가 있습니다. 정확히 M개의 치킨집을 남길 때, 각 집의 치킨 거리는 남긴 치킨집 중 가장 가까운 곳까지의 맨해튼 거리입니다. 도시의 치킨 거리는 모든 집의 치킨 거리를 합한 값이며, 이 합을 최소화해야 합니다.
순열이 아니라 조합을 열거합니다. DFS는 치킨집 인덱스를 오름차순으로 선택하므로 같은 집합을 순서만 바꾸어 중복 계산하지 않습니다. start는 다음 선택에서 허용되는 첫 인덱스이고, selected는 현재까지 고른 치킨집 인덱스입니다. M개를 모두 골랐으면 각 집을 순회해 선택된 치킨집까지의 최소 거리를 구하고, 그 합으로 최솟값을 갱신합니다.
분기하기 전에 remaining = C - start를 아직 선택 가능한 치킨집 수, needed = M - selected.size()를 앞으로 골라야 할 수로 둡니다. remaining < needed이면 이 분기에서는 필요한 개수를 채울 수 없으므로 가지치기합니다. 남은 후보 수와 필요한 수가 같을 때는 조건을 만족하지 않으므로 경계에 해당하는 분기도 탐색합니다. M = 1이면 각 치킨집 하나씩을 평가하고, M = C이면 가능한 조합 하나를 평가합니다.
완성된 조합은 C개 중 M개를 고르는 경우의 수만큼 있으며, 조합 하나를 평가하는 데 O(H*M) 시간이 듭니다. 따라서 시간 복잡도는 O((C choose M) * H*M)입니다. 집 목록, 치킨집 목록, 현재 선택 목록의 공간 복잡도는 O(H+C)입니다. 거리 합산에는 long long을 사용합니다.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
struct Point {
int row;
int col;
};
int m;
vector<Point> homes;
vector<Point> stores;
vector<int> selected;
long long answer = numeric_limits<long long>::max();
int manhattan(const Point &a, const Point &b) {
return abs(a.row - b.row) + abs(a.col - b.col);
}
void search(int start) {
if (static_cast<int>(selected.size()) == m) {
long long total = 0;
for (const Point &home : homes) {
int nearest = numeric_limits<int>::max();
for (int index : selected) {
nearest = min(nearest, manhattan(home, stores[index]));
}
total += nearest;
}
answer = min(answer, total);
return;
}
const int needed = m - static_cast<int>(selected.size());
const int remaining = static_cast<int>(stores.size()) - start;
if (remaining < needed) return;
for (int i = start; i <= static_cast<int>(stores.size()) - needed; ++i) {
selected.push_back(i);
search(i + 1);
selected.pop_back();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n >> m;
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
int cell;
cin >> cell;
if (cell == 1) homes.push_back({row, col});
else if (cell == 2) stores.push_back({row, col});
}
}
search(0);
cout << answer << '\n';
}