10971. 외판원 순회 2

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

import sys
input = sys.stdin.readline

n = int(input())
link = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
min_cost = float('inf')

def dfs(start, current, count, cost):
    global min_cost

    # 모든 도시를 방문하고 시작점으로 돌아왔을 때
    if count == n and link[current][start] > 0:
        min_cost = min(min_cost, cost + link[current][start])
        return

    # 가지치기: 현재 비용이 최소 비용보다 크면 중단
    if cost >= min_cost:
        return

    for i in range(n):
        if not visited[i] and link[current][i] > 0:
            visited[i] = True
            dfs(start, i, count + 1, cost + link[current][i])
            visited[i] = False

# 모든 도시를 시작점으로 탐색
for i in range(n):
    visited[i] = True
    dfs(i, i, 1, 0)
    visited[i] = False

print(min_cost)