외판원 순환 (작은 N)

### 문제 도시 $N$개가 있다. $i$번 도시에서 $j$번 도시로 가는 비용 $D_{i, j}$가 주어진다 ($i \ne j$이면 양의 정수, $i = j$이면 0). 비용은 비대칭일 수 있다 ($D_{i,j} \ne D_{j,i}$일 수 있음). 당신은 **0번 도시에서 출발**해서, 모든 도시를 정확히 한 번씩 방문한 뒤 다시 **0번 도시로 돌아오는** 순환 경로를 만들려고 한다. 가능한 모든 순환 경로 중 비용의 합이 **최소**인 것을 구하라. ### 순열로 전탐색 0번에서 출발해 나머지 $N-1$개 도시를 방문하는 순서를 정하는 일이다. $N-1$개의 순열을 모두 시도하면 $(N-1)!$가지. $N = 10$이면 $9! = 362880$이라 1초 안에 가능. 각 순열의 비용은 한 번 순회로 $O(N)$이니 전체 $O(N \cdot N!) \approx O(N \cdot (N-1)!)$.