https://en.wikipedia.org/wiki/Travelling_salesman_problem 굉장히 유명한 NP-hard 문제라 주어진 조건만으로는 절대 풀 수 없는 문젠데 혹시 문제에 빠져있는 다른 조건이 존재하나요?

n이 최대 1000이므로 NP-hard여도 생각보다 오래 걸리지 않습니다. 파이썬으로 1000ms 이내에 풀 수 있는 테스트케이스만 넣어두었습니다. 그냥 푸셔도 됩니다 감사합니다

넵.. 그래도 이 글을 보는 다른 분들을 위해 정정하자면 이 문제 푸는 알고리즘이 메모리가 무한하다는 가정하에 O(n^2 * 2^n)이고 그렇지 않으면 O(n!)이라서 n이 1000이면 정말 오래 걸리는 게 맞아요..