BOJ 15686: 치킨 배달 (c++)

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

int N, M;
vector<pair<int, int>> houses;
vector<pair<int, int>> chickens;
int minDistance = INT_MAX;
vector<bool> selected;

// 거리 계산
int calculateCityChickenDistance() {
    int total = 0;
    for (auto& h : houses) {
        int dist = INT_MAX;
        for (int i = 0; i < chickens.size(); ++i) {
            if (selected[i]) {
                int d = abs(h.first - chickens[i].first) + abs(h.second - chickens[i].second);
                dist = min(dist, d);
            }
        }
        total += dist;
    }
    return total;
}

// 백트래킹
void backtrack(int idx, int count) {
    if (count == M) {
        minDistance = min(minDistance, calculateCityChickenDistance());
        return;
    }

    for (int i = idx; i < chickens.size(); ++i) {
        selected[i] = true;
        backtrack(i + 1, count + 1);
        selected[i] = false;
    }
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int val;
            cin >> val;
            if (val == 1) houses.push_back({i, j});
            else if (val == 2) chickens.push_back({i, j});
        }
    }

    selected.resize(chickens.size(), false);
    backtrack(0, 0);

    cout << minDistance << '\n';
    return 0;
}

 

M개를 선택하는 모든 경우를 백트레킹으로 찾기

각 조합마다 거리 계산

최소 찾아 출력