[ 백준 15686 ] 치킨 배달 (C++) - BruteForce, 조합

---

🔗 문제 링크

15686번: 치킨 배달

---

💡 문제 풀이 및 해석

1. 치킨집은 13개 이하, 그냥 집은 최대 2N 이다.
2. 조합으로 13개를 뽑는다면, 최대 13C6 이다.
3. 따라서 1716 * 2 * 50 이므로 브루트포스하게 풀 수 있다.
4. 이제 치킨집을 고른 뒤, 집마다 치킨집까지의 거리를 구하고 가장 가까운 거리를 계속 더해주면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#define INF 987654321

using namespace std;

int N, M;
int answer = INF;
vector<pair<int, int>> chikenShop;
vector<pair<int, int>> home;
vector<vector<int>> myMap;

void input() {
    cin >> N >> M;
    myMap = vector<vector<int>>(N, vector<int>(N, 0));
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> myMap[y][x];
            if (myMap[y][x] == 1) {
                home.push_back({ y,x });
            }
            else if (myMap[y][x] == 2) {
                chikenShop.push_back({ y,x });
            }
        }
    }
}

int chikenDist(vector<pair<int, int>> myPick) {
    int totalDist = 0;
    for (pair<int, int> myHome : home) {
        int dist = INF;
        for (pair<int, int> shop : myPick) {
            dist = min(dist, abs(shop.first - myHome.first) + abs(shop.second - myHome.second));
        }
        totalDist += dist;
    }
    return totalDist;
}

void sol(int index, vector<pair<int,int>> myPick) {
    if (myPick.size() == M) {
        answer = min(answer, chikenDist(myPick));
        return;    
    }

    for (int i = index; i < chikenShop.size(); i++) {
        myPick.push_back(chikenShop[i]);
        sol(i + 1, myPick);
        myPick.pop_back();
    }

    return;
}

int main() {

    input();
    vector<pair<int, int>> myPick;
    sol(0, myPick);
    cout << answer;

    return 0;
}

---

🤔 문제 후기

브루트포스하게 할 수 있다는 것만 안다면, 그렇게 어려운 문제는 아니였던 것 같다. 최근에 조합문제를 풀어본 적이 있어서 비교적 쉽게 풀 수 있었던 것 같다. 아마, 조합을 풀어본 적이 없거나 오래전에 풀었다면, 골드5 난이도의 문제로 느껴지진 않았을 것 같다.