5189. [파이썬 SW 문제해결 구현] 2일차 - 전자카트

예시에서 연결이 1-2-3-1, 1-3-2-1 이런식으로 두개라는 것을 보고 딱 봐도 순열이라고 생각했다.

[1,2,3] 개가 주어질 경우 맨 왼쪽, 맨 오른쪽은 1로 고정되어 있으니 [2,3] 끼리의 순열만을 생각한다.

import sys

sys.stdin = open("sample_input.txt", "r")

import itertools
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = int(input())

    route = [list(map(int, input().split())) for _ in range(N)]

    cb = list(itertools.permutations(range(2,N+1),r=N-1))

    distance = []
    for tup in cb:
        sub_distance = 0
        sub_distance += route[0][tup[0]-1]
        for i in range(len(tup)-1):
            sub_distance += route[tup[i] - 1][tup[i+1] - 1]
        sub_distance += route[tup[len(tup)-1]-1][0]
        distance.append(sub_distance)

    print("#{}".format(test_case),min(distance))

    # ///////////////////////////////////////////////////////////////////////////////////