https://www.acmicpc.net/problem/2098
<aside> 💡 외판원 순회2: https://www.acmicpc.net/problem/10971 놀랍게도 얘는 실버 2밖에 안된다. 더더욱 놀랍게도 둘의 차이는 N의 최댓값이 10이냐 16이냐의 차이일 뿐. 그 차이때문에 외판원 순회2는 브루트포스, 백트래킹으로 해결된다. 근데 그러면 worst case가 O(N!)인게 문제.
</aside>
1초 128MB
외판원 순회(TSP: Traveling Salesman Problem) CS에서 중요하게 취급되는 문제 중 하나라고 합니다. 여러 가지 변형이 있지만, 2098에서는 기본형 문제를 알려준다고 한다.
1번부터 N번까지 N개의 도시가 있고, 각 도시 사이에는 길이 있을 수도 있고 없을 수도 있다. 길에는 비용이 있고 방향성이 있다.
한 외판원이 어느 한 도시에서 출발하여 N개의 도시를 모두 방문하고, 처음의 도시로 돌아오려 한다. 이 때 한 번 방문한 도시는 다시 방문할 수 없다. (마지막에 첫 도시로 돌아오는 것은 제외)
상기 조건을 만족하는 경로가 여러 개 있을 수 있는데, 비용이 가장 적게 드는 경로를 찾아야 한다.
W[i][j] = i에서 j로 가기 위한 비용 비용은 대칭이 아니기 때문에 W[i][j]와 W[j][i]가 다를 수도 있다. 모든 비용은 양의 정수이다. W[i][i]는 항상 0이다. i에서 j로 갈 수 없는 경우 W[i][j] = 0이다.
첫째 줄에 도시 개수 N (2≤ N ≤ 16)
다음 N개의 줄에 비용 행렬 (0≤ e ≤ 1,000,000) (0 → 갈 수 없음, 나머지 양의 정수 → 이동 비용)
순회 불가능한 경우는 입력으로 주어지지 않음
외판원 순회의 최소 비용을 출력