[Codetree] 외판원 순회 Python

https://www.codetree.ai/missions/2/problems/traveling-salesman-problem/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

n = int(input())

graph = []

for _ in range(n):
    temp = list(map(int, input().rstrip().split(" ")))
    graph.append(temp)


num = [i for i in range(1, n)]
visited = [0 for _ in range(n-1)]


cnt = 100000
answer = []


def find_cost(temp):
    answer = []
    cnt = 0

    for i in range(len(temp)-1):
        answer.append([temp[i], temp[i+1]])

    for i, j in answer:
        if graph[i][j] == 0:
            return 0
        cnt += graph[i][j]
    
    return cnt



def backtrack(dep):
    global cnt

    if dep == n-1:
        temp = [0] + answer[::] + [0]
        if find_cost(temp) != 0:
            cnt = min(find_cost(temp), cnt)
        return

    for i in range(n-1):
        if not visited[i]:
            answer.append(num[i])
            visited[i] = 1
            backtrack(dep+1)
            answer.pop()
            visited[i] = 0

backtrack(0)

print(cnt)