15661: 링크와 스타트

• [스타트와 링크] 문제와 마찬가지 방식으로 접근함
• 팀원 수가 일치하지 않는 경우까지 고려해야하므로 N//2 이하의 depth를 모두 순회해야함

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 * (N-1)
def dfs(flag, n):
    global min_gap
    if len(visit) == n:
        start = 0
        for x in range(n):
            for y in range(x, n):
                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(N-n):
            for y in range(x, N-n):
                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, n)
            visit.pop()

for f in range(1, N//2 + 1):
    dfs(0, f)
print(min_gap)