백준 15686번 치킨배달

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

위 문제는 모든 경우의 수를 다 탐색해야하는 문제이며 백트래킹 알고리즘을 적용해야 한다.

예를들어 5개의 치킨집이 있고, 그 중 2개를 방문해야 한다면

1. 1 1 0 0 0

2. 1 0 1 0 0

3. 1 0 0 1 0

   ...

   ...

   0 0 0 1 1

까지 모든 경우의 수를 탐색해야 한다.

최대 M 개의 치킨집을 찾았다면 해당 case 에서 최소 거리가 되는 치킨거리를 구한다.

이후 위에서 설명한 모든 경우의 수에서 최소 거리가 되는 치킨거리를 구하면 된다.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
vector<pair<int, int>> clients;
vector<pair<int, int>> stores;
bool visit[13] = {false, };
int result = 987654321;
int getDist() {
    int cl = clients.size();
    int sl = stores.size();
    int ret = 0;
    
    for (int i = 0 ; i < cl; ++i) {
        int tempDist = 987654321;
        for (int j = 0; j < sl; ++j) {
            if (visit[j]) {
                tempDist = min(tempDist, (abs(clients[i].first - stores[j].first) + abs(clients[i].second - stores[j].second)));
            }
        }
        ret += tempDist;
    }
    return ret;
}
// start (totalStoreLength, startStoreIndex, curSelectedStoreCnt)
void start (int sl, int idx, int cnt, int nck) {
    if (cnt >= nck) {
        int sum = getDist();
        result = result > sum ? sum : result;
        return ;
    }
    
    for (int i = idx; i < sl; ++i) {
        visit[i] = true;
        start(sl, i + 1, cnt + 1, nck);
        visit[i] = false;
        start(sl, i + 1, cnt, nck);
    }
}
int main()
{
    int n, nck, t;
    
    scanf("%d %d", &n, &nck);
    for (int i = 1 ; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int t;
            scanf("%d", &t);
            if (t == 1) {
                clients.push_back(make_pair(i, j));
            } else if (t == 2) {
                stores.push_back(make_pair(i, j));
            }
        }
    }
    
    start(stores.size(), 0, 0, nck);
    printf("%d\n", result);
    return 0;
}