(C++) - 백준(BOJ) 15686번 : 치킨배달 답

www.acmicpc.net/problem/15686

15686번: 치킨 배달

비트마스킹을 이용해 m개 이하의 치킨집을 연 후 치킨거리를 게산하여 최솟값을 출력하는 문제였습니다.

 

풀이방법 

 시간복잡도 : (살릴 치킨집을 고르는 시간) * (다 고른 후 도시의 치킨 거리를 구하는 시간) = (2^m) * n^2 

 1. n^n의 격자에서 입력 받을 때 집의 좌표와 치킨집의 좌표를 각자 저장합니다.

 

 2. 비트마스킹을 이용해 치킨집이 열려있는 상태를 표시할 수 있습니다.

 

   2-1. i개의 치킨집들 중 최대 m개를 선택하여 나올 수 있는 최소 도시치킨 거리를 찾습니다. 비트마스킹으로 모든 상태를 표시하므로 연 치킨집의 수가 m개를 초과하면 치킨거리를 구하지 않습니다.

 

   2-2. 각자 집의 좌표에 대해 치킨집의 좌표들 까지의 맨해튼 거리를 구해 최소를 구하고 도시치킨 거리의 좌표에 더해줍니다. 이렇게 모든 집의 좌표에 대해 도시치킨 거리의 좌표를 구하면 거리를 반환해줍니다. 

 

 3. 이들 치킨 거리들 중 최소를 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n,m;
int city[51][51];
int ans = 0x3f3f3f3f;
struct home { int x,y; };
struct chicken { int x,y,opened; };

vector <home> homes;
vector <chicken> chickens;

int getDistance(int x1, int y1, int x2, int y2){
    return abs(x1-x2) + abs(y1-y2);
}

int getChickDist(){
    int dist = 0;
    for(int i = 0; i < homes.size(); i++){
        int tmp = 101;
        for(int j = 0; j < chickens.size(); j++){
            if(chickens[j].opened){
                int x1 = homes[i].x;
                int y1 = homes[i].y;
                int x2 = chickens[j].x;
                int y2 = chickens[j].y;
                tmp = min(tmp, getDistance(x1,y1,x2,y2));
            }
        }
        dist += tmp;
    }
    return dist;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> city[i][j];
            if(city[i][j] == 1) homes.push_back({i,j});
            else if(city[i][j] == 2) chickens.push_back({i,j,0});
        }
    }

    for(int i = 0; i < (1 << chickens.size()); i++){
        int chickenStat = 0;
        int tmp = i;
        while(tmp){
            chickenStat += tmp % 2;
            tmp/= 2;
        }
        if(chickenStat > m) continue;
        for(int j = 0; j < chickens.size(); j++){
            chickens[j].opened = i & (1<<j);
        }
        ans = min(ans,getChickDist());
    }
    cout << ans;
}