테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 세계 일주 ======

===== 풀이 =====
  * 유클리디안 거리를 이용하는 TSP 문제.
  * 이미 지난 점을 다시 지날수 없다는 제한이 걸려있다. 이 것을 바꿔 말하면, 경로들이 서로 교차하면 안된다는 뜻인다. 그런데 유클리디안 TSP에서 교차하는 경로를 갖는 경로는 최단 경로가 될수 있다는 것은 잘 알려져 있는 사실이다. 결국, 최단경로는 제한에 위배될 일이 없으므로, 제한에 신경쓸 필요 없이, 그냥 최단 경로를 구하면 끝이다.
  * TSP는 비트마스킹 DP를 이용해서 O(n*2^n)에 푸는 방법이 잘 알려져있지만, 이 문제에서는 제한이 10으로 작기 때문에, 그냥 모든 경로를 일일히 따져보는 O(n*n!) 브루트 포싱으로 처리해도 풀린다. 완전 나이브하게 구현하면 TLE이지만 약간의 가지치기만 추가해도 통과 가능하다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31219. 세계 일주".

- Problem link: https://www.acmicpc.net/problem/31219
- Solution link: http://www.teferi.net/ps/problems/boj/31219

Tags: [tsp]
"""

import math
import itertools

INF = float('inf')


def main():
    n = int(input())
    coords = [[int(x) for x in input().split()] for _ in range(n)]

    answer = INF
    for path in itertools.permutations(coords):
        tot_dist = 0
        for p, q in itertools.pairwise([*path, path[0]]):
            tot_dist += math.dist(p, q)
            if tot_dist >= answer:
                break
        else:
            answer = tot_dist

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}