14889: 스타트와 링크

• 능력치를 빠르게 search 할 수 있는 방법을 구해보려 했다가 그냥 안구함
• person list를 만들고 N/2의 depth로 dfs를 오름차순으로 순회하여 팀을 구성할 수 있는 모든 경우의 수를 구함
• link팀의 선수는 start팀의 선수와 중복되지 않고, 선수는 중복되지 않으므로, person list를 person_set으로 변경해주고 visit list를 visit_set으로 변경해주어 이 둘의 차집합인 link팀을 구함
• gap은 local minimum, min_gap은 global minimum임

import sys

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

person = [_ for _ in range(N)]
person_set = set(person)
visit = []

min_gap = 200 * (int(N/2))
def dfs(flag):
    global min_gap
    if len(visit) == int(N/2):
        start = 0
        for x in range(int(N/2)):
            for y in range(x, int(N/2)):
                start += tmp[visit[x]][visit[y]] + tmp[visit[y]][visit[x]]
        
        visit_set = set(visit)
        team_link = list(person_set - visit_set)
        link = 0
        for x in range(int(N/2)):
            for y in range(x, int(N/2)):
                link += tmp[team_link[x]][team_link[y]] + tmp[team_link[y]][team_link[x]]

        gap = abs(start - link)
        min_gap = min(min_gap, gap)
        return
    for i in range(flag, N):
        if person[i] not in visit:
            visit.append(person[i])
            dfs(i)
            visit.pop()

dfs(0)
print(min_gap)