백준 10971번 외판원의 순회 2

1. 시간초과 순열로 모든 경우의 수를 check해서 그런지 느리다

import sys

def permutations(ref, n):
    ans = []
    if n > len(ref): return ans

    if n == 1:
        for item in ref: ans.append([item])
    elif n>1:
        for i in range(len(ref)):
            temp_ref = ref[:]
            temp_ref.remove(ref[i]) ## 순열의 정의에 따라 자유롭게 remove 메소드를 사용해도 되겠습니다.
            for p in permutations(temp_ref, n-1):
                ans.append([ref[i]]+p)
    return ans

if __name__ == '__main__':
    city_num = int(sys.stdin.readline())
    city = []
    city_name = dict()
    city_sequence = []
    for sequence in range(city_num):
        city_sequence.append(sequence)
    sum = 0
    pre_min = 10000
    for x in range(city_num):
        city_value = map(int,sys.stdin.readline().split())
        for y in city_value:
            city.append(y)
        
        city_name[x] = city
        city = []
    #print(city_sequence, city_name)
    for i in permutations(city_sequence,city_num):
        i = i + [i[0]]
        lens = len(i)-1
        for j in range(lens):
            if city_name[i[j]][i[j+1]] == 0:
                #print(i[j], i[j+1], city_name[i[j]], city_name[i[j]][i[j+1]])
                sum = 0
                break
            #print(i[j], i[j+1], city_name[i[j]], city_name[i[j]][i[j+1]])
            sum += city_name[i[j]][i[j+1]]
        if sum < pre_min and sum >0:
            pre_min = sum
        sum = 0
    print(pre_min)

## 코드 정리 성공 or 시간초과 랜덤하게 발생 ##

import sys
from itertools import permutations
cnt = int(sys.stdin.readline())
matrix = []
for i in range(cnt):
    row = list(map(int, sys.stdin.readline().split()))
    matrix.append(row)
min_cost = float(“inf”)
for route in permutations(range(cnt)):
    route = (*route, route[0])
    total_cost = 0
    is_valid = True
    for i in range(len(route)-1):
        fr, to = route[i], route[i+1]
        cost = matrix[fr][to]
        total_cost += cost
        if cost <= 0 or total_cost >= min_cost:
            is_valid = False
            break
    if is_valid:
        min_cost = total_cost
print(min_cost)

2. dfs를 사용예정