[伯俊]セールスマン問題2(TSP)

[白俊]https://www.acmicpc.net/problem/10971
[注]https://shoark7.github.io/programming/algorithm/introduction-to-tsp-and-solve-with-exhasutive-search
[フルナビゲーション]
[問題定義]
しゅつりょく
startからnext経由でN都市を訪問し,startから都市に戻るのに必要な距離パターンの最大値を求める.
問題値
都市個数N、ある都市から別の都市までの距離dist
ループ関数
現在の都市(next)から次の都市(for文中i)までを決定し、距離を増やします.
再帰関数に必要なパラメータ
(都市数:N)
start都市のidx:start
next都市のidx:next
アクセス都市リスト:アクセス済み=[]
これまでの距離コスト:コスト
さいきふっきじょうけん
すべての都市を訪問
再帰反復コード
0からn-1までのn都市への経路
都市アクセス可能条件

以前にアクセスしたことがありません=>(アクセスリストの表示)

この都市への道が必要=>(dist[next][i]確認)

# ----[input]-------------------------------------------------
import sys
sys.stdin = open('text/TSP.txt', 'r')
n = int(input())
dist =[]
for i in range(n):
	dist.append(list(int(i) for i in input().split()))
# -----------------------------------------------------------

min = 9999999

def dfs(start, next, visited, cost):
	global min

	if len(visited) == n:
		# 리턴 조건: 모든 도시 방문함?
		if dist[next][start] != 0:
			cand = cost + dist[next][start]	# 최소거리 후보
			min = min if cand > min else cand			# 둘 중 작은 값 택
		return

	else:
		# 아직 안함
		for i in range(n):
			if dist[next][i] != 0 and i not in visited:
				# and i != start 참고 코드에 이게 포함되어있는데 없어도 될 것 같음
				# 어차피 처음 함수 호출할 때 시작도시를 visited에 넣으니까
				visited.append(i)
				dfs(start, i, visited, cost + dist[next][i])
				visited.pop()

# 각 도시마다 시작
for i in range(n):
	# 시작도시를 저장하는 start변수와 별개로 next는 현재 위치한 도시를 의미하므로
	# 처음 함수를 호출할 때는 start와 next를 똑같이 할당해야 한다.
	dfs(i, i, [i], 0)

print(min)