[C++] 삼성 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

#include<iostream>
#include<vector>
#include<math.h>
 
using namespace std;
 
vector<pair<int, int>> save;
bool check[12] = { false, };
int min_dist;
 
int cal_dist(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
 
void solution(int start_index, int dist, int size) {
    if (size == save.size() - 2) {
        dist += cal_dist(save[start_index], save[1]);
        if (min_dist > dist)
            min_dist = dist;
        return;
    }
 
    for (int i = 2; i < save.size(); i++) {
        if (check[i] == false && i!=start_index) {
            check[i] = true;
            solution(i, dist + cal_dist(save[start_index], save[i]), size + 1);
            check[i] = false;
        }
    }
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        min_dist = 9999999;
        int N, x, y;
        cin >> N;
        for (int i = 0; i < N+2; i++) {
            cin >> x >> y;
            save.push_back(make_pair(x, y));
        }
        solution(0, 0, 0);
        cout << "#" << t << " " << min_dist << endl;
        save.clear();
    }
 
    return 0;
}