[백준] 10971 : 외판원 순회 2 python

 

 

import sys
input = sys.stdin.readline
 
def dfs(depth, start, value):
    global min_value
    # n개의 도시를 모두 방문했을 때 시작점으로 돌아가는 길이 있다면
    if depth == n and graph[start][0]!=0:
    	# 이번 탐색에 소요된 비용과 지금까지 구해둔 최소비용과 비교함
        min_value = min(min_value,value+graph[start][0])
        return
        
    # 이미 최소비용을 넘겼다면 더 탐색할 필요가 없음
    if value>min_value:
        return
        
    for i in range(n):
    	# 아직 방문하지 않았고 갈 수 있는 도시가 있다면
        if visited[i]==0 and graph[start][i]!=0:
        	# 방문하고 거기서 탐색을 더 함
            visited[i]=1
            dfs(depth+1,i,value+graph[start][i])
            # 방문 해제
            visited[i]=0
 
n = int(input())
min_value = sys.maxsize
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))
visited = [0]*n
 
visited[0]=1
dfs(1,0,0)
print(min_value)