[C++] Samsung SW Expert Academy 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

/*

Basic DFS(or BFS) problem.






*/

#include <iostream>

using namespace std;

struct myPair {
int x;
    int y;
};
myPair comp,home;
myPair cust[10];
int result;
int visit[10];


int dist(myPair p1, myPair p2) {
int temp = abs(p1.x - p2.x);
    int temp2 = abs(p1.y - p2.y);
 
    return temp + temp2;
}

void dfs(int N, int prev, int cur, int sum, int count) {
    if(prev == -1) {
        sum = dist(comp,cust[cur]);
    }
    else {
        if (visit[cur] == 1) {
            return;
        }

        sum += dist(cust[prev],cust[cur]);
    }
 

    visit[cur] = 1;
    count++;
 
    if(count >= N) {
        sum += dist(cust[cur],home);
        result = min(result,sum);
        visit[cur] = 0;
        return;
    }
 
    for(int d=0;d<N;d++) {
    dfs(N,cur,d,sum,count);
    }
    visit[cur] = 0;

}

void calc(int N){
    for(int i=0;i<N;i++) {
        dfs(N,-1,i,0,0);
    }
}

int main() {
    int T;
    cin >> T;
 
    for(int k=1;k<=T;k++){
        int N;
        cin >> N;
     
        cin >> comp.x;
        cin >> comp.y;
        cin >> home.x;
        cin >> home.y;

        for(int i=0;i<N;i++){
        cin >> cust[i].x;
            cin >> cust[i].y;
        }
     
     
        for(int i=0;i<N;i++) visit[i] = 0;
        result = 2000000000;
     
calc(N);
     
        cout << "#" << k << " " << result << endl;
 
    }
return 0;
 
}