[BOJ]17182번: 우주 탐사선

 

www.acmicpc.net/problem/17182

---

시작점에서 출발해서 모든 점을 전부 순회할 때 최솟값을 구하는 문제입니다.

 

문제 조건이 MST나 단순 다익스트라와는 약간 다릅니다.

 

1. 플로이드를 통해 모든 정점쌍 간의 최소거리를 구합니다.

2. N제한이 작으므로 순열을 통해 방문할 순서를 미리 정한 후 순서대로 방문해봅니다.

 

위 과정을 통해 가장 짧은 경로를 구할 수 있습니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ17182.cc