10971: 외판원 순회 2

• dfs를 이용하여 모든 도시들을 순회함
• len(nodes) == N일 때, 가격을 계산하기 시작함
  -> min_value가 global minimum value임 (해당 경우마다 min_value를 갱신해줌)
  -> 길이 없는 경우에는 바로 return 해줌
  -> 마지막에는 처음 출발했던 도시로 돌아와야하므로 value += W[nodes[j]][nodes[0]]

import sys

N = int(input()); W = []
for _ in range(N):
    W.append(list(map(int, sys.stdin.readline()[:-1].split(' '))))

visit = [False] * N
nodes = []

min_value = 1000000 * N
def dfs():
    global min_value
    if len(nodes) == N:
        value = 0
        for j in range(1, N):
            if W[nodes[j-1]][nodes[j]] == 0:
                return
            else:
                value += W[nodes[j-1]][nodes[j]]
        if W[nodes[j]][nodes[0]] == 0:
            return
        else:
            value += W[nodes[j]][nodes[0]]
        min_value = min(min_value, value)
        return
    for i in range(N):
        if not visit[i]:
            nodes.append(i); visit[i] = True
            dfs()
            nodes.pop(); visit[i] = False

dfs()
print(min_value)