[link](https://www.acmicpc.net/problem/15686) ```cpp #include <algorithm> #include <iostream> #include <string> #include <vector> #include<math.h> using namespace std; int map[51][51], N, M, answer = 50 * 100 * 50; struct axis { int y, x; }; struct home { int y, x; int distance[13]; }; vector<home> house; vector<axis> chicken; bool visited[13]; int get_distance(home h, axis a) { return abs(h.y - a.y) + abs(h.x - a.x); } void dfs(int depth, int count, int sum) { if (sum > answer) { return; } if (chicken.size() - count == M) { int new_answer = 0; for (home h : house) { int min_distance = h.distance[0]; for (int i = 0; i < chicken.size(); i++) { min_distance = min(min_distance, h.distance[i]); } new_answer += min_distance; if (new_answer > answer) { return; } } //cout << new_answer << "\n"; //for (bool b : visited) { // cout << b; //} //cout << endl; answer = min(answer, new_answer); return; } visited[depth] = 1; dfs(depth + 1, count + 1); visited[depth] = 0; dfs(depth + 1, count); } void solution() { cin >> N >> M; for (int y = 0; y < N; y++) { for (int x = 0; x < N; x++) { cin >> map[y][x]; switch (map[y][x]) { case 1: home temp_home; temp_home.y = y; temp_home.x = x; house.push_back(temp_home); break; case 2: axis temp_axis; temp_axis.y = y; temp_axis.x = x; chicken.push_back(temp_axis); break; } } } // 모든 치킨집과의 거리 계산 for (int home_index = 0; home_index < house.size(); home_index++) { for (int i = 0; i < chicken.size(); i++) { house[home_index].distance[i] = get_distance(house[home_index], chicken[i]); } } dfs(0, 0); cout << answer << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solution(); return 0; } ```
Activity