외판원 순회3 16991번 [백준]

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

16991번: 외판원 순회 3

 

이미 외판원 순회를 풀어 보았지만, 시간이 오래 지나서 복습을 할겸 외판원 순회3을 풀어보았다. 

 

한번 풀어본 문제였음에도 고생을 많이 하였다.

 

이 문제는 dp문제로 dp문제답게 어느부분이 겹치는지를 확인해야 한다.(시작점은 어디로 두든지 상관이 없다.)

겹치는 부분을 저장하기 위해 vector<vector<double>> [n][2의 16승]을 활용하였다. 

 

해당 dp는 시작 point와 지금까지 어느곳을 방문했는지를 기점으로 반복을 없앨 수 있다.

이 문제를 풀면서 배운점은 dp문제를 풀 때 어떤 case들이 겹치는지를 확인하고 해당 유형에 맞게 dp의 구조를 설정하는 것이 핵심이라는 것이다.

 

이번 문제에서는 기존과 다르게 단순히 visited만을 겹친다고 간주하게 되면 문제풀이에 차질이 생긴다.

그래프를 따라서 어느점에서 어느점으로 단순히 방문한 곳만 따지기에는 dp의 값에 혼선이 생긴다.

 

그 이유는 dp[visited]의 최솟값은 시작점이 0~15까지 모두를 알아야 구할 수 있기 때문이다.

이렇게 구하게 되면 이 모든 값을 구하고 난 뒤에는 이미 다 구했으므로 값이 쓸모가 없어진다.

즉 dp을 쓰는 의미가 없다는 뜻이다.

 

#include<bits/stdc++.h>
#include<sys/types.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define v(n) vector<n>
typedef long long ll;

int n;
v(pii) arr;
double matrix[16][16];
vector<vector<double>> dp(16, vector<double>(65537, -1.0));//{vistied,ans}
double minimum(int visited, int start) {//0에서 시작
    if (visited == (1 << n) - 1) {
        return matrix[start][0];
    }
    if (dp[start][visited] != -1.0) {
        return dp[start][visited];
    }
    double tmp = 99999999999.0;
    rep(i, 16) {
        if (!(visited & (1 << i)))
            tmp = min(tmp, matrix[start][i] + minimum(visited | (1 << i), i));
    }
    dp[start][visited] = tmp;
    return tmp;
}

void solve() {

    cin >> n;
    arr = vector<pii> (n);
    for (auto &x: arr) {
        cin >> x.ff;
        cin >> x.ss;
    }
    rep(i, n) {
        rep(j, n) {
            if (i == j)continue;
            matrix[i][j] = sqrt(pow(arr[i].ff - arr[j].ff, 2) + pow(arr[i].ss - arr[j].ss, 2));
        }
    }
    cout << minimum(1, 0);
}

int main() {
    fast_io;
    cout << fixed;
    cout.precision(6);
    solve();
    return 0;
}