1247. 최적 경로

TSP 문제로 볼 수 있다. 

문제에 모든 경우의 수를 확인하면 된다고 적혀있으므로 모두 구하는 방법도 있고

비트마스크로 dp를 사용하는 방법도 있다.

모든 경우의 수는 next_permutation을 사용하면 쉽게 가능하지만 2200ms나 걸리고 dp를 사용하면 6ms가 나온다.

dp테이블은 d[현재위치][현재 방문상태 비트마스크] 형식이다.

<순열 코드>

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
struct po {
    int x, y;
};
 
int t, n;
int pm[12];
po a[12];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n;
        int ans = 2e9;
        cin >> a[0].x >> a[0].y >> a[n + 1].x >> a[n + 1].y;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i].x >> a[i].y;
            pm[i] = i;
        }
        pm[n + 1] = n + 1;
        do {
            int sum = 0;
            for (int i = 1; i <= n + 1; ++i) 
                sum += abs(a[pm[i]].x - a[pm[i - 1]].x) + abs(a[pm[i]].y - a[pm[i - 1]].y);
            ans = min(ans, sum);
        } while (next_permutation(pm + 1, pm + 1 + n));
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}

<dp 코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
 
typedef long long ll;
struct po {
    int x, y;
};
 
int t, n;
int d[11][1 << 11], e;
int dist[12][12];
po a[12];
// cur_position, bitmask
int dp(int f, int x) {
    int &ret = d[f][x];
    if (ret != -1) return ret;
    if (x == e) 
        return dist[f][n + 1];
    ret = 2e9;
    for (int i = 1; i <= n; ++i) {
        if (x&(1 << i)) continue;
        ret = min(ret, dp(i, x | (1 << i)) + dist[f][i]);
    }
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        memset(d, -1, sizeof(d));
        cin >> n;
        int ans = 2e9;
        e = (1 << (n + 1)) - 1;
        cin >> a[0].x >> a[0].y >> a[n + 1].x >> a[n + 1].y;
        for (int i = 1; i <= n; ++i) 
            cin >> a[i].x >> a[i].y;
        for (int i = 0; i < n + 2; ++i) for (int j = 0; j < n + 2; ++j)
            dist[i][j] = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y);
        
        cout << "#" << tc << " " << dp(0, 1) << '\n';
    }
    return 0;
}