[BOJ 15686] 치킨 배달(C++)

치킨 배달(Gold 5)

문제

전체 문제 보기

15686번: 치킨 배달

접근법

이번 문제는 입력받은 전체 치킨집들 중에서 M개를 선택했을 때 도시의 치킨 거리가 가장 작게 되도록 만들어야 합니다. 이번 문제는 선택 가능한 모든 경우의 수를 탐색하면서 도시의 치킨 거리를 계산하여 풀 수 있는 문제입니다.

 

M의 최대값은 13이며, 치킨집의 개수는 M이상 13 이하입니다. 따라서 최악의 경우에는 13개의 치킨 집 중 6개 혹은 7개를 선택하는 경우 가장 오래 걸립니다. (참고. 13개의 치킨집 중에서 13개를 선택하는 경우의 수는 하나뿐입니다.) 13개의 치킨 집 중 6개를 구하는 경우의 수는 다음과 같이 1,716 가지가 있습니다.

\[_{13}\mathrm{C}_{6} = \frac{13!}{6!\cdot7!} = 1,716 \]

 

 따라서 최악의 경우에도 도시의 치킨 거리를 1,716번만 계산하면 되기 때문에 충분히 시간 내에 풀이 가능합니다.

자료구조 및 알고리즘 선택

에서 먼저 이번 문제를 풀기 위한 자료구조는 다음과 같이 선택하였습니다.

struct Pos
{
    Pos(int _r, int _c) : r{ _r }, c{ _c }{}
    Pos() {}
    int r;
    int c;
};
struct Chicken
{
    Chicken(int _r, int _c) : pos{ _r, _c } {}
    Pos pos;
    bool selected{};
};

vector<Chicken> chickens; // 치킨집 위치정보와 선택 여부를 담고있는 배열
vector<Pos> houses;          // 도시의 집 위치정보를 담고 있는 배열

도시의 치킨 거리는 chickens 배열과 house 배열을 활용하여 다음과 같이 계산할 수 있습니다.

// 집에서 가장 가까운 치킨집 까지의 거리 
int GetMinDistance(const Pos& house, const vector<Chicken>& chickens)
{
    const int r = house.r;
    const int c = house.c;
    int retval{ INF };
    for (const auto& chicken : chickens)
    {
        if (chicken.selected == false) continue;
        retval = min(retval, abs(r - chicken.pos.r) + abs(c - chicken.pos.c));
    }
    return retval;
}
// 도시의 치킨거리, 모든 집에 대해서 치킨 거리의 최소값을 계산후 누적 합산
int CityChickenDist(vector<Pos>& houses, vector<Chicken>& chickens)
{
    int retval{};
    for (const auto& house : houses)
    {
        const int result = GetMinDistance(house, chickens);
        retval += result;
    }            
    return retval;
}

지금까지 도시의 치킨 거리를 계산하는 방법을 살펴봤습니다. 이제 전체 치킨집에서 M개를 선택하는 방법에 대해서 살펴보겠습니다. M개 이상의 치킨집에서 M개를 선택할 때는 백트레킹 알고리즘을 사용할 수 있습니다. 백트레킹 알고리즘을 활용해서 다음과 같이 모든 선택에 대해서 탐색을 진행할 수 있습니다. 우리가 구해야 할 경우의 수는 조합이기 때문에 다음 깊이의 탐색을 진행할 때 매개변수로 i+1 을 넘겨주는 것에 유의해야 합니다.

int BT(vector<Pos>& houses, vector<Chicken>& chickens, int idx, int numOfChicken, int M)
{
    int retval{ INF };
    if (numOfChicken == M)
    {
        retval = CityChickenDist(houses, chickens);
        return retval;
    }
    for (size_t i = idx; i < chickens.size(); ++i)
    {
        // i번째 치킨집을 이미 탐색했다면 continue
        if (chickens[i].selected == true) continue;

        // i번째 치킨집 선택
        chickens[i].selected = true;

        // 다음 탐색 
        retval = min(retval, BT(houses, chickens, i + 1, numOfChicken + 1, M));

        // i번째 치킨집 복구
        chickens[i].selected = false;
    }
    return retval;
}

전체 구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'
using namespace std;
constexpr int INF = 87'654'321;
struct Pos
{
    Pos(int _r, int _c) : r{ _r }, c{ _c }{}
    Pos() {}
    int r;
    int c;
};
struct Chicken
{
    Chicken(int _r, int _c) : pos{ _r, _c } {}
    Pos pos;
    bool selected{};
};

void InputData(vector<Pos>& houses, vector<Chicken>& chickens, int N)
{
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int temp;
            cin >> temp;
            if (temp == 1)
                houses.emplace_back(i, j);
            else if (temp == 2)
                chickens.emplace_back(i, j);
        }
    }
}
int GetMinDistance(const Pos& house, const vector<Chicken>& chickens)
{
    const int r = house.r;
    const int c = house.c;
    int retval{ INF };
    for (const auto& chicken : chickens)
    {
        if (chicken.selected == false) continue;
        retval = min(retval, abs(r - chicken.pos.r) + abs(c - chicken.pos.c));
    }
    return retval;
}

int CityChickenDist(vector<Pos>& houses, vector<Chicken>& chickens)
{
    int retval{};
    for (const auto& house : houses)
    {
        const int result = GetMinDistance(house, chickens);
        retval += result;
    }            
    return retval;
}

int BT(vector<Pos>& houses, vector<Chicken>& chickens, int idx, int numOfChicken, int M)
{
    int retval{ INF };
    if (numOfChicken == M)
    {
        retval = CityChickenDist(houses, chickens);
        return retval;
    }
    for (size_t i = idx; i < chickens.size(); ++i)
    {
        // i번째 치킨집을 이미 탐색했다면 continue
        if (chickens[i].selected == true) continue;

        // i번째 치킨집 선택
        chickens[i].selected = true;

        // 다음 탐색 
        retval = min(retval, BT(houses, chickens, i + 1, numOfChicken + 1, M));

        // i번째 치킨집 복구
        chickens[i].selected = false;
    }
    return retval;
}
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, M; // N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)
    cin >> N >> M;
    vector<Chicken> chickens;
    vector<Pos> houses;
    InputData(houses, chickens, N);

    int answer = BT(houses, chickens, 0, 0, M);
    cout << answer << endl;

    return 0;
}