[C++] 백준 - 15686 : 치킨 배달

문제 링크

15686번: 치킨 배달

 

 

풀이 )

  입력으로 받은 집과 치킨집을 각각 home, chic vector에 넣어줬다.

  풀고나서 보니 city는 한번도 안썼다.

 

  이후 길이가 chic vector에서 1개를 시작으로 m개까지의 조합을 만들어 선택된 치킨집을 이용해 sum( )을 호출하여 치킨 거리를 계산한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<pair<int, int> > chic;
vector<pair<int, int> > home;

int calc(pair<int, int> chic, pair<int, int> home){
    return abs(chic.first-home.first)+abs(chic.second-home.second);
}

int sum(vector<int> picked){
    int hLen = home.size();
    int pLen = picked.size();
    int ret = 0;

    for(int i = 0; i < hLen; ++i){
        int tmp = 1e9;
        for(int j = 0; j < pLen; ++j)
            tmp = min(tmp, calc(home[i], chic[picked[j]]));
        ret += tmp;
    }

    return ret;
}

int dfs(vector<int> picked, int cLen, int pos, int cnt){
    if(cnt == 0)
        return sum(picked);

    int ret = 1e7;
    for(int i = pos; i < cLen; ++i){
        picked.push_back(i);
        ret = min(ret, dfs(picked, cLen, i+1, cnt-1));
        picked.pop_back();
    }
    return ret;
}

int main(void){
    cin >> n >> m;
    vector<vector<int> > city(n, vector<int>(n));

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> city[i][j];
            if(city[i][j] == 2)
                chic.push_back({i, j});
            if(city[i][j] == 1)
                home.push_back({i, j});
        }
    }

    int cLen = chic.size();
    int ans = 1e7;
    for(int i = 1; i <= m; ++i)
        ans = min(ans, dfs(vector<int>(0), cLen, 0, i));
    cout << ans << '\n';
}