https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)의 범위를 보고 완전 탐색을 해도 된다는 것을 알 수 있다.
(r1, c1)과 (r2, c2)의 거리는 문제에서 주어졌듯이
|r1-r2| + |c1-c2|
다음과 같은 식을 사용해서 풀 수 있다. BFS로도 풀 수 있지만 위의 식을 이용해서 간단히 풀 수 있다.
먼저 입력을 받을 때, 집과 치킨집의 좌표를 각각 벡터에 넣어준다.
그다음에는 치킨집 중 m개를 고르는 경우를 모두 구해준 후에
각각 m개를 골라줬을 때마다 도시의 치킨 거리를 구해주고 최솟값을 비교하여 저장한다.
치킨 거리는 모든 집에 대해서 구해줘서 각 집의 치킨 거리를 전체 도시 치킨 거리에 더해준다.
각 집의 치킨 거리는 각 집으로부터 폐업하지 않은 모든 치킨집과의 거리를 구해보고
최소 거리가 치킨 거리가 된다.
|
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m;
int ans;
int map[50][50];
vector<pair<int, int>> home;
vector<pair<int, int>> store;
vector<pair<int, int>> selected;
int calc() {
int citylen = 0;
int homecnt = home.size();
int hx, hy, sx, sy;
//모든 집에대해 치킨거리를 구한다.
for (int i = 0; i < homecnt; i++) {
hx = home[i].first;
hy = home[i].second;
int chickenlen = 10000;
//모든 치킨집과의 거리를 계산하여 가장 가까운 곳이 치킨거리이다
for (int j = 0; j < m; j++) {
sx = selected[j].first;
sy = selected[j].second;
int tmp = abs(hx - sx) + abs(hy - sy);
chickenlen = min(chickenlen, tmp);
}
//도시의 치킨거리에 i번째 집의 치킨거리를 더해준다.
citylen += chickenlen;
}
//도시의 치킨 거리를 리턴
return citylen;
}
void select(int index, int cnt) {
//m개를 골랐다
if (cnt == m) {
//도시의 치킨거리를 계산한다.
int tmp = calc();
ans = min(ans, tmp);
return;
}
//모든 가게에 대해 선택을 끝냈다.
if (index == store.size()) return;
int x = store[index].first;
int y = store[index].second;
//index번째 가게를 폐업시키지 않는 경우
selected.push_back(make_pair(x, y));
select(index + 1, cnt + 1);
//index번째 가게를 폐업시키는 경우
selected.pop_back();
select(index + 1, cnt);
}
int main() {
ios_base::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];
//집인 경우 home벡터에 추가, 치킨집인 경우 store벡터에 추가
if (map[i][j] == 1) home.push_back(make_pair(i, j));
else if (map[i][j] == 2) store.push_back(make_pair(i, j));
}
}
//ans에 정답이 될 수 있는 값보다 큰 값을 넣어둔다.
ans = 10000;
//탐색 시작
select(0, 0);
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 14502. 연구소 (0) | 2019.08.04 |
|---|---|
| [BOJ] 15685. 드래곤 커브 (0) | 2019.08.04 |
| [BOJ] 16234. 인구 이동 (0) | 2019.08.02 |
| [BOJ] 17281. ⚾ (0) | 2019.08.02 |
| [BOJ] 17136. 색종이 붙이기 (0) | 2019.08.02 |