[백준/Python] 외판원 순회 2

문제

설명

N개의 도시를 모두 순회하는 가장 짧은 비용을 찾아내는 TSP문제이다. 같은 도시는 중복으로 가면 안되기에 순열로 모든 조합을 나열하여 완전 탐색으로 풀었다. 1번 도시부터 N번 도시까지 걸리는 비용을 더하고 마지막으로 N번 도시에서 1번 도시로 돌아오는 비용을 더해주었다.

Python3로 제출하면 시간초과가 났는데, PyPy3로 제출하니까 통과가 되어서 찾아봤는데, Python3의 실행 시간이 오래 걸려서 개선하고자 만든게 PyPy3인데 모든 경우에 PyPy3가 속도가 우세한 것은 아니라고 한다. 따라서 상황에 맞춰 적철하게 사용하라고 읽었는데, 아직 어떤 상황에 무엇을 적용해야 할 지는 모른다.

구현

from itertools import permutations

n = int(input())
li = [i for i in range(n)]
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 2e9

for elem in permutations(li):
    temp = 0
    flag = False
    cost = [100000 if arr[elem[i]][elem[i+1]] == 0 else arr[elem[i]][elem[i+1]] for i in range(len(elem)-1)]
    temp = sum(cost)
    
    temp += 100000 if arr[elem[-1]][elem[0]] == 0 else arr[elem[-1]][elem[0]]
    ans = min(ans, temp)
    
print(ans)