백준 15686번: 치킨 배달 (C++)

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

비교적 간단한 조합 / 백트래킹 / 전수조사 문제이다.

문제를 보면, 결국 모든 경우의 수를 조사해야 하는 상황이다. 따라서 집의 위치와, 치킨집의 위치를 따로 벡터에 담아주고,

백트래킹을 활용해서 치킨집을 m개 선택한 다음, 선택한 치킨집을 가지고 치킨 거리를 구하면 되겠다.

이 경우에 다시 일반 가정집을 검색할 필요가 없도록, 미리 초반에 일반집도 벡터에 담아두고 사용하면 되겠다.

[소스코드]

#include<iostream>
#include<vector>
#include<math.h>
#include<limits.h>

using namespace std;
int map[52][52], n, m, st = 0, arr[14];
 
vector<pair<int, int > > v, hv; //치킨집, 가정집
 
int res = INT_MAX;
bool isused[14];
void process() {//집마다 치킨집 여러개와의 거리가 있는데, 그 거리의 최소값의 합을 구한다
    int cityDis = 0;

    for (int i = 0; i < hv.size(); i++) {
        int Min = INT_MAX;
        for (int j = 0; j < m; j++) {
            int sumR = 0, sumC = 0;
            sumR += abs(hv[i].first - v[arr[j]].first);
            sumC += abs(hv[i].second - v[arr[j]].second);
            if (sumR + sumC < Min) Min = sumR + sumC;
        }
        cityDis += Min; //도시의 치킨거리
    }

    if (res > cityDis) res = cityDis; //도시의 치킨거리 최댓값 갱신 
}

void backTracking(int k) { //조합 템플릿
    if (k == m) {
        //arr에 치킨벡터 인덱스
        process();
        return;
    }

    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}

int main(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 2) v.push_back({ i, j }); //치킨집
            else if (map[i][j] == 1) hv.push_back({ i, j }); //가정집
        }
    }
    
    backTracking(0);
 
    cout << res << '\n';
    return 0;
}