[15686] 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

<문제>

치킨집의 개수를 x라 하면, m개의 1, (x-m)개의 0으로 구성된 배열을 next_permutation으로 모든 경우를 만들어준다.

치킨집의 위치와 집의 위치를 미리 별도의 자료구조로 저장해둔다면,

단순히 next_permutation의 결과가 0일때에만 continue하면서 거리를 구해줄 수 있다.

하나의 집을 기준으로 할때, 가장 가까운 치킨집 하나만 계산해야 하므로 항상 최소값으로 갱신해주고,

갱신된 최소값 하나만 최종 결과에 누적시켜주어야 한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, a[60][60];
vector<pair<int, int>> home;
vector<pair<int, int>> pos;
int getDist(vector<int> base) {
    int ret = 0;
    for (auto& start : home) {
        int cur = 1e9;
        for (int end = 0; end < base.size(); end++) {
            if (base[end] == 0) continue;
            int score = abs(start.first - pos[end].first) +
                        abs(start.second - pos[end].second);
            cur = min(score, cur);
        }
        ret += cur;
    }
    return ret;
}
int main(void) {
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 2) pos.push_back({i, j});
            if (a[i][j] == 1) home.push_back({i, j});
        }
    int S = pos.size();
    vector<int> base(S);
    for (i = 0; i < m; i++) base[i] = 1;
    sort(base.begin(), base.end());
    int ans = 1e9;
    do {
        int score = getDist(base);
        ans = min(score, ans);
    } while (next_permutation(base.begin(), base.end()) == true);
    cout << ans;
    return 0;
}