[10/12] 14889 (스타트와 링크)

실버3 문제
백트래킹 (실패)

내 코드

from itertools import combinations

n = int(input())
arr = []
player = list(range(n))

for _ in range(n):
    temp = list(map(int, input().split()))
    arr.append(temp)
    
answer = 99999
for i in combinations(player, n//2):
    start = list(i)
    link = list(set(player) - set(start))
    
    start_list = list(combinations(start, 2))
    link_list = list(combinations(link, 2))
    
    start_sum = 0
    for x, y in start_list:
        start_sum += (arr[x][y] + arr[y][x])
        
    link_sum = 0
    for x, y in link_list:
        link_sum += (arr[x][y] + arr[y][x])
        
    answer = min(answer, abs(start_sum - link_sum))
    if (start[0] != 0 or answer == 0):
        break
        
print(answer)

로직

• 백트래킹으로 푸는 방법 공부 필요