[C++][백준 31219] 세계 일주

문제

접근 방법

처음에는 선분 교차 + TSP인 줄 알았다.

https://upload.acmicpc.net/f8f45639-ed47-4369-80ec-f97b210f6537/
최적해가 항상 두 번째 조건을 만족하기에 TSP 알고리즘만으로 해결된다.

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using pii = pair<int, int>;
#define INF 987654321
vector<pii> countries;
int n, fullBitMask;
float answer = INF;
float getDistance(pii a, pii b)
{
    float sub1 = a.first - b.first;
    float sub2 = a.second - b.second;
    return sqrt(sub1 * sub1 + sub2 * sub2);
}
void dfs(int cur, float sum, int bitMask)
{
    if (sum >= answer)
    {
        return;
    }
    if (fullBitMask == bitMask) // 모두 방문한 경우
    {
        float distance = getDistance(countries[cur], countries[0]);
        answer = min(answer, sum + distance);
        return;
    }
    for (int i = 1; i < n; ++i)
    {
        if ((bitMask & (1 << i))) // 이미 방문했다면
        {
            continue;
        }
        float distance = getDistance(countries[cur], countries[i]);
        dfs(i, sum + distance, (bitMask | (1 << i)));
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    cout << fixed;

    countries = vector<pii>(n);
    fullBitMask = (1 << n) - 1;

    for (pii &country : countries)
    {
        cin >> country.first >> country.second;
    }

    dfs(0, 0, 1 << 0);
    cout << answer;
}

풀이

불가능한 경우가 존재하지 않기에 굳이 -1을 출력할 일은 없다.
두 번째 조건을 무시해도 된다는 것을 눈치채면 쉬워지는데 그렇지 않으면 어려운 것 같다.

푸는 도중에 에디토리얼을 안 봤다면 힘들었을 것 같다.