백준 15686. 치킨 배달
구현 문제
4년전에 제대로 이해하지도 못하고 답보고 풀었는데, 이제 좀 이해가 된다
조합과 구현이 합쳐진 문제
문제 분석
N*N인 도시
각 칸은 빈칸, 치킨집, 집 중 하나이다
치킨 거리란? : 집과 가장 가까운 치킨집 사이의 거리
각각의 집은 “치킨 거리”를 가지고 있다.
도시의 치킨 거리는 모든 집들의 “치킨 거리”의 합이다
그런데, 이 도시에 있는 치킨 집 중 일부를 폐업시키려 한다
도시에 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개일때, 나머지는 모두 폐업시켜야한다
어떻게 고르면, 도시의 치킨 거리가 가장 작게 될 지 구하는 프로그램을 작성하기
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어짐
둘째줄 부터 N개의 줄에 도시의 정보가 주어짐
0은 빈칸, 1은 집, 2는 치킨집을 의미한다
집의 개수는 2N을 넘지 않으며, 적어도 한개는 존재한다.
치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다
출력
폐업시키지 않을 치킨집 M개를 골랐을 때, 도시의 치킨 거리의 최소값을 출력하기
예제 분석
1)
1
2
3
4
5
6
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
최대 3개만 남기고 폐업 시켜야함
근데 이미 치킨집이 3개있음 -> 폐업 안해도 된다
(0,2) - (1,2) = 1 (1,4) - (1,2) = 2 (2,1) - (2,2) = 1 (3,2) - (2,2) = 1
치킨 거리의 최소값 5
2)
1
2
3
4
5
6
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
최대 2개만 남기고 폐업시켜야한다
맵에서 치킨집 두개를 고르고(조합 : 5C2) 나머지 폐업시킨뒤, 거리를 체크해야함
(0,1)과 (4,4)를 남기면
(0,3), (1,0), (1,2), (3,3) => 2 (3,4), (4,3) => 1 도시의 치킨 거리의 최소값은 10이다
알고리즘
M의 개수에 따라 치킨집을 몇개 고를건지가 정해진다.
먼저 맵에서 현재 치킨집이 몇개인지 체크한 뒤, M개만 고르는 과정을 거처야함
X_C_M : x개의 치킨집에서 M개의 치킨집만을 남기고 모두 박살냄
이후 이 선택된 치킨집들과 각 집의 치킨 거리를 계산하여 최소값들만 더한다
계산한 값을 최소값과 비교 후 갱신하면 될듯
1
2
3
4
5
6
7
8
9
10
11
12
13
1. 전처리
- N, M 입력받기
- 지도 입력받기
- 1이라면 house 벡터에 좌표를 저장
- 2라면 chicken 벡터에 좌표를 저장한다
2. x개의 치킨집 중 m개의 치킨집 뽑기. (dfs던 next_permutation 이용)
- m개의 치킨집을 선택한다
- house벡터에 저장된 집들에 대해서 다음을 수행한다
- 남은 치킨집들과의 거리를 계산 후, 최소값을 계산한다
- 이 최소값을 현재 도시 치킨거리에 더한다
- 최소 기록이라면 이를 갱신한다
3. 최소 도시 치킨 거리 출력 후 종료
시간 복잡도 계산
집의 개수는 최대 2N = 2 * 50 = 100개
치킨집의 개수는 최대 13개이다.
근데 여기서 M개를 골라야하는데, 최악의 경우 13C6 = 13!/(6!*7!) = 1716가지가 나온다
하나의 조합당 집의 총 개수 * 치킨집의 총 개수를 계산하면 최대 1300번의 연산이 필요하다
총 시간 복잡도는 : O((X Choose M) * 집의 개수 * 치킨집의 개수)이므로
1716 * 100 * 13 = 2230800 약 223만번이다.
근데 치킨집 고르는건 최악의 경우에 1716가지인거지, 13개 고르면 1300번만 연산하면됨
즉, 2,230,800보다 작으므로, 충분히 통과 가능함
소스코드
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
65
66
67
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int N, M, min_dis = 21e8;
struct Point {
int y;
int x;
};
vector<Point> houses;
vector<Point> chickens;
void Input() {
// freopen("input.txt", "r", stdin);
cin >> N >> M;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
int input; cin >> input;
if (input == 1) {
houses.push_back({ y,x });
}
else if (input == 2) {
chickens.push_back({ y,x });
}
}
}
}
// 맨해튼 거리 계산기
int CalcDistance(Point A, Point B) {
return abs(A.y - B.y) + abs(A.x - B.x);
}
void DFS(int level, int next, vector<int>& selected_indices) {
// M개를 모두 선택했을 때
if (level == M) {
int city_dis = 0;
for (Point house : houses) {
int this_house_dis = 21e8;
for (int idx : selected_indices) {
this_house_dis = min(this_house_dis, CalcDistance(house, chickens[idx]));
}
city_dis += this_house_dis;
}
min_dis = min(min_dis, city_dis);
return;
}
for (int i = next; i < chickens.size(); i++) {
selected_indices.push_back(i); // 선택
DFS(level + 1, i + 1, selected_indices);
selected_indices.pop_back(); // 복구
}
}
int main() {
Input();
vector<int> selected_indices; // 이 치킨집이 선택되어있는지 체크하는 용도
DFS(0, 0, selected_indices);
cout << min_dis;
return 0;
}