[코드트리] 외판원 순회 Python

# n 입력
n = int(input())
# costs
costs = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# get_min_cost(curr_path)
def get_min_cost(curr_path):
    # curr_loc, curr_cost
    curr_loc, curr_cost = 0, 0

    for next_loc in curr_path:
        # 비용이 0인게 있으면
        if not costs[curr_loc][next_loc]:
            # 최대비용 처리
            return sys.maxsize
        # 비용을 내고
        curr_cost += costs[curr_loc][next_loc]
        # 움직여주기
        curr_loc = next_loc
    
    # 마지막 비용이 0이면
    if not costs[curr_loc][0]:
        # 최대비용처리
        return sys.maxsize 
    
    # 처음으로 돌아오기
    curr_cost += costs[curr_loc][0]

    # 반환
    return curr_cost

# simulate(curr_idx)
def simulate(curr_idx):
    # 전역변수 선언
    global min_cost

    # 종료조건
    if curr_idx == n-1:
        # min_cost update
        min_cost = min(min_cost, get_min_cost(path))
        return
    # 차례 만들어주기
    for i in range(1, n):
        if visited[i]:
            continue
        
        path.append(i)
        visited[i] = True
        
        simulate(curr_idx + 1)

        path.pop()
        visited[i] = False

# 설계
# min_cost
import sys
min_cost = sys.maxsize

# path, visited
path, visited = [], [False for _ in range(n)]

# simulate
simulate(0)

# 출력
print(min_cost)