SW Expert Academy 1247 최적 경로 - C++

이 문제는 그 유명한 외판원의 순회와 비슷하다.

문제에도 대놓고 적혀 있는 만큼, 

문제를 효율적으로 푸는 것이 중요한 것이 아니다.

비트 마스킹과 DP를 이용하면 조금 더 빨리 풀 수 있지만,

가벼운 완전탐색으로도 풀리는 문제이다.

 

가독성을 위해 거리를 구하는 함수를 따로 뺐고,

구현의 간편함을 위해 dfs로 구현한다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int T, N;
int x[12], y[12];
bool used[12];
int tmpMax;
 
int absDist(int x1, int y1, int x2, int y2) {
    int ret = 0;
    ret += x1 > x2 ? x1 - x2 : x2 - x1;
    ret += y1 > y2 ? y1 - y2 : y2 - y1;
    return ret;
}
 
int dfs(int n=0, int curCost=0, int idx=0) {
    if (n==N){
        tmpMax = min(tmpMax, curCost + absDist(x[idx], y[idx], x[1], y[1]));
        return 0;
    }
    for (int i = 2; i < N + 2; ++i) {
        if (!used[i]) {
            used[i] = true;
            dfs(n + 1, curCost+absDist(x[i],y[i],x[idx],y[idx]),i);
            used[i] = false;
        } 
    }
    return 0;
}
 
int solve() {
    tmpMax = 987654321;
    dfs();
    return tmpMax;
}
 
int main() {
    scanf("%d", &T);
    for (int test = 1; test <= T; ++test) {
        scanf("%d", &N);
        for (int i = 0; i < N+2; ++i) {
            scanf("%d", &x[i]);
            scanf("%d", &y[i]);
        }
        printf("#%d %d\n", test, solve());
    }
}