[백준] 15686 치킨 배달(C++)

 

문제 URL:

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

집과 가장 가까운 치킨집 사이의 거리를 치킨 거리라고 할 때 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|이다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시킬 때 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하자.

 

이 문제는 브루트포스 알고리즘을 이용하는 문제로 모든 경우를 다 확인해 보아야 한다. 이 과정에서 백트래킹이 이용된다. 

치킨집을 M만큼 선택하고 선택한 치킨집들과 각각의 집들의 치킨 거리를 구하고, 각각의 집에서의 치킨 거리를 모두 더해주어 도시의 치킨 거리를 구한다. 치킨집을 선택하는 과정에서 백트래킹을 이용하여 선택하는 치킨집을 다르게 만들어준다. 치킨집을 다르게 한 각 경우마다 도시 치킨 거리를 구하고 이를 비교하여 최소 도시 치킨 거리를 출력해주면 된다. 

---

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

int N, M, answer;
int MAP[50][50];
int isSelect[13];
vector<pair<int, int>> House, Chicken, V;

int distance(){  // 치킨 거리를 구하는 함수
    int sum = 0;
    for (int i = 0; i < House.size(); i++){
        int x = House[i].first;
        int y = House[i].second;
        int d = 99999999;
        for (int j = 0; j < V.size(); j++){
            int xx = V[j].first;
            int yy = V[j].second;
            int dist = abs(xx - x) + abs(yy - y);
            d = min(d, dist);
        }
        sum = sum + d;
    }
    return sum;
}

void Select_Chicken(int idx, int cnt){  // 치킨집을 선택하는 함수
    if(cnt == M){
        answer = min(answer, distance());
        return;
    }
    for(int i = idx; i < Chicken.size(); i++){
        if(isSelect[i] == 1)
            continue;

        isSelect[i] = 1;
        V.push_back(Chicken[i]);
        Select_Chicken(i, cnt + 1);
        // 백트래킹
        isSelect[i] = 0;
        V.pop_back();
    }
}

int main(){
    answer = 99999999;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> MAP[i][j];
            if(MAP[i][j] == 1)
                House.push_back(make_pair(i, j));
            if(MAP[i][j] == 2)
                Chicken.push_back(make_pair(i, j));
        }
    }

    Select_Chicken(0, 0);
    cout << answer << '\n';

    return 0;
}

출처: [ 백준 15686 ] 치킨배달 (C++) :: 얍문's Coding World.. (tistory.com)