[알고리즘/백준] 10971번 : 외판원 순회 2(python)

permutation으로 풀면 시간 초과가 난다.

백트래킹으로 풀었다.
처음 번호, 현재 번호, 합, 갯수를 넘겨주었다.
만약 갯수가 N과 같다면 제일 마지막 도시이기 때문에 처음 도시로 가는 비용을 추가하고 작은지 큰지 비교한다.

import sys


def dfs(start, now, value, cnt):
    global ans
    if cnt == N:
        if a[now][start]:
            value += a[now][start]
            if ans > value:
                ans = value
        return

    if value > ans:
        return

    for i in range(N):
        if not visited[i] and a[now][i]:
            visited[i] = 1
            dfs(start, i, value + a[now][i], cnt + 1)
            visited[i] = 0


N = int(input())
a = [list(map(int, input().split()))for _ in range(N)]
ans = sys.maxsize
visited = [0] * N
for i in range(N):
    visited[i] = 1
    dfs(i, i, 0, 1)
    visited[i] = 0
print(ans)