문제
풀이
dfs를 통해 치킨집을 고르는 모든 조합을 선택해준다.
1
2
3
4
5
6
7
8
9
10
11
void chooseChicken(vector<Pos> &choice, int L, int idx) {
if (L == M) {
minDist = min(minDist, getChickenDistance(choice));
return;
}
for (int i = idx; i < chicken.size(); i++) {
choice.push_back(chicken[i]);
chooseChicken(choice, L + 1, i + 1);
choice.pop_back();
}
}
선택 된 치킨집들에서 getDistance 함수를 통해 min값을 갱신해준다.
1
2
3
4
5
6
7
8
9
10
int getChickenDistance(vector<Pos> &choice) {
int ret = 0;
for (const auto &h : house) {
int sum = INF;
for (const auto &c : choice)
sum = min(sum, (abs(h.y - c.y) + abs(h.x - c.x)));
ret += sum;
}
return ret;
}
이제 전체 소스 코드를 살펴보자.
소스 코드
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
#include <algorithm>
#include <cstdlib> // abs
#include <iostream>
#include <vector>
using namespace std;
const int INF = 987654321;
int city[51][51];
int N, M, minDist = INF;
struct Pos {
int y, x;
};
vector<Pos> house, chicken;
int getChickenDistance(vector<Pos> &choice) {
int ret = 0;
for (const auto &h : house) {
int sum = INF;
for (const auto &c : choice)
sum = min(sum, (abs(h.y - c.y) + abs(h.x - c.x)));
ret += sum;
}
return ret;
}
void chooseChicken(vector<Pos> &choice, int L, int idx) {
if (L == M) {
minDist = min(minDist, getChickenDistance(choice));
return;
}
for (int i = idx; i < chicken.size(); i++) {
choice.push_back(chicken[i]);
chooseChicken(choice, L + 1, i + 1);
choice.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
// 입력
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
cin >> city[i][j];
if (city[i][j] == 1)
house.push_back({i, j});
else if (city[i][j] == 2)
chicken.push_back({i, j});
}
vector<Pos> temp;
chooseChicken(temp, 0, 0);
cout << minDist << '\n';
return 0;
}
