[백준][Python][10971][브루트포스] 외판원 순회 2

문제 : https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

외판원 순회 Traveling Salesman problem 는 유명한 NP-Complete 문제다.

O(N!)의 어마어마한 복잡도를 가지는 문제이므로 순열도 부담없이 사용했다.

 

문제 풀이는 다음과 같다.

1. 1-n 사이의 모든 순열을 만든다.
2. 수열 하나하나마다:
   1. 1-2,....n-2 - n-1번째 까지 주어진 맵을 보며 길이 있나 확인하고 없으면(0) 이면 -1 return 한다. 있으면 weight를 더한다
   2. 있는경우 n-1 - n 을 확인해서 길이 있나 확인하고 있으면 더하고 아니면  -1 return.
   3. 모든 순열에 대해 min을 확인해서 답을 낸다.

 

from itertools import permutations

n = int(input())

d = []
for i in range(n):
    d.append([int(a) for a in input().split()])


perm = [i for i in range(n)]

answer = 9123491234

def sum_routes(r):
    global d,n
    tmp = 0
    for i in range(len(r)-1):
        if d[r[i]][r[i+1]] !=0:
            tmp+=d[r[i]][r[i+1]]
        else:
            return -1

    if d[r[-1]][r[0]] ==0:
        return -1
    else:

        tmp+=d[r[-1]][r[0]]
    
    return tmp




for c in permutations(perm):
    tmpans = sum_routes(c)
    if tmpans!= -1:
        answer = min(answer, tmpans)
    

print(answer)