백트래킹

스타트와 링크

문제 풀이 전략:
1.두 팀으로 나눔
2. 스타트팀과 링크팀에서 각각 2명씩 조합을 이루어 낼 수 있는 시너지를 모두 더함
3. 스타트팀 - 링크팀의 값이 가장 작은 값을 출력

핵심 코드

for i in list(combinations(lst, n // 2)):
	start = set(i)
	link = set(lst) - start

from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
graph = []
for i in range(n):
	graph.append(list(map(int, input().split())))
lst = [i for i in range(n)]
result = 987654321
for i in list(combinations(lst, n // 2)):
	start = set(i)
	link = set(lst) - start
	startSum = 0
	linkSum = 0
	for j in list(combinations(start, 2)):
		startSum += graph[j[0]][j[1]]
		startSum += graph[j[1]][j[0]]
	for k in list(combinations(link, 2)):
		linkSum += graph[k[0]][k[1]]
		linkSum += graph[k[1]][k[0]]
	if abs(startSum - linkSum) < result:
		result = abs(startSum - linkSum)
print(result)