출처: https://www.acmicpc.net/problem/15686
문제 설명
NxN grid위에 위치한 두 점(a, b), (c, d) 사이의 거리를 r = abs(a-c) + abs(b-d)로 정의한다. 문제에서는 각 집에서 가장 가까운 치킨집까지의 거리를 그 집의 치킨거리로 하고, 모든 집의 치킨 거리의 합을 도시의 치킨 거리로 한다.
치킨집의 수를 줄이고, 이때 도시의 치킨거리 최소값을 구하는 문제이다.
입력
N M
NxN
0 - 길, 1 - 집, 2 - 치킨집
출력
도시 치킨 거리 최소값
입력 예
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
출력 예
10
제약조건
2 <= N <=50 , 1 <= M <=13
문제 풀이
N x N Grid를 읽어 들이면서 집의 위치와 치킨집의 위치를 vector<pair<int, int>> 에 저장한다.
치킨집 배열에서 M개를 고르고, 이 때 각 집들에서 치킨 거리를 구하고, 그 합을 비교해서 최소값을 찾는다.
M개를 고르기 위해서, bitset을 이용해서, 치킨집들을 선택한다.
프로그램 내용
더보기
...
bitset<MAX_M> bsets;
int min_dist = INT_MAX;
vector<pair<int, int>> t_shops;
for(int b = 0; b < (1<<(int)shops.size()); ++b)
{
if (__builtin_popcount(b) == tM)
{
bsets = b; /// 해당하는 치킨집 조합 결정
for(int id=0; id< (int)shops.size();++id)
{
if(bsets[id])
{
t_shops.push_back(shops[id]);
}
}
int t_dist = 0;
for(int id = 0; id<(int)house.size(); ++id)
{
int h_dist = INT_MAX;
int ht_dist = INT_MAX;
int x, y;
tie(x, y) = house[id];
for(int idn = 0; idn < (int)t_shops.size(); ++idn)
{
int t_x, t_y;
tie(t_x, t_y) = t_shops[idn];
int hh_dist = abs(x - t_x) + abs(y - t_y);
if( ht_dist > hh_dist)
ht_dist = hh_dist;
}
if (h_dist > ht_dist) /// 각 집의 치킨거리 최소값
h_dist = ht_dist;
t_dist += h_dist;
}
t_shops.clear();
if( min_dist > t_dist) /// 도시 치킨 거리 최소값
min_dist = t_dist;
}
}
관련된 문제
- bitset : USACO Trainging : 2.1.6 Healthy Holsteins ( link )
'Baekjoon Online Judge' 카테고리의 다른 글
| BOJ 23970 알고리즘 수업 - 버블 정렬 3 (0) | 2022.02.13 |
|---|---|
| BOJ 2824 최대공약수 (0) | 2021.12.03 |
| BOJ 2903 - 중앙 이동 알고리즘 (0) | 2020.01.28 |
| BOJ 17404 - RGB거리 2 (0) | 2019.12.10 |