BOJ 15686 - 치킨 배달

출처: 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 )