15686 치킨 배달

15686 치킨 배달

1. 치킨집을 m개 고르는 모든 경우에 대해 백트래킹 한다.

2. 골라진 경우마다 최소값을 구한다.

3. 최소값을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
#define P pair<int,int>
using namespace std;
 
int n, m, res;
int d[100][14];//각각 지원자들의 고사장과의 거리 저장
bool visited[14];
vector<P> p; //고사장 위치 저장
vector<P> h; //지원자 위치 저장
 
int get_result() {
    int ans = 0;
    for (int i = 0; i < h.size(); i++) {
        int min_dist = INF;
        for (int j = 0; j < p.size(); j++) {
            if (visited[j]) min_dist = min(min_dist, d[i][j]);
        }
        ans += min_dist;
    }
    return ans;
}
 
void dfs(int idx, int cnt) {
    visited[idx] = true;
 
    if (cnt == m) {
        //최소비용 계산
        res = min(res, get_result());
    }
    else {
        for (int i = idx + 1; i < p.size(); i++) {
            dfs(i, cnt + 1);
        }
    }
 
    visited[idx] = false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 1) h.push_back(P(i, j));
            else if (x == 2) p.push_back(P(i, j));
        }
    }
 
    //거리 미리 저장해놓기
    for (int i = 0; i < h.size(); i++) {
        for (int j = 0; j < p.size(); j++) {
            d[i][j] = abs(h[i].first - p[j].first) + abs(h[i].second - p[j].second);
        }
    }
    res = INF;
    //고사장을 m개 고르는 모든 경우에 대해 백트래킹
    for (int i = 0; i < p.size(); i++) {
        dfs(i, 1);
    }
 
    cout << res << "\n";
}